Gramatyki zwykłe i bezkontekstowe

Przygotowuję się do testu z języków komputerowych i jest jeden pomysł, że mam problemy ze zrozumieniem.

Zrozumiałem, że zwykłe gramatyki są prostsze i nie mogą zawierać niejednoznaczności, ale nie mogą wykonywać wielu zadań wymaganych w językach programowania. Zrozumiałem również, że gramatyki bezkontekstowe pozwalają na niejednoznaczność, ale pozwalają na pewne rzeczy niezbędne dla języków programowania (np. Palindromy).

To, z czym mam problem, to zrozumienie, w jaki sposób mogę wyprowadzić wszystkie powyższe informacje, wiedząc, że nieterminały gramatyki regularnej mogą mapować do terminala lub nieterminala, po którym następuje terminal, lub że bezkontekstowe mapowanie nieterminala do dowolnej kombinacji terminali i nieterminali .

Czy ktoś może mi pomóc połączyć to wszystko razem?

Gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa to w zasadzie dowolna kombinacja terminali i nieterminali. Stąd widać, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej.

Na przykład dla palindromu ma postać

S->ABA
A->something
B->something

Widać wyraźnie, że palindromów nie można wyrazić w gramatyce regularnej, ponieważ musi być liniowa w prawo lub w lewo i jako taka nie może mieć nieterminalnego wyrażenia po obu stronach.

Ponieważ gramatyki regularne nie są niejednoznaczne, istnieje tylko jedna reguła produkcji dla danego nieterminala, podczas gdy w przypadku gramatyki bezkontekstowej może być więcej niż jedna.

Myślę, że chcesz pomyśleć o różnych lemmatach o pompowaniu. Język regularny może zostać rozpoznany przez automat skończony. Język bezkontekstowy wymaga stosu, a język wrażliwy na kontekst wymaga dwóch stosów (co jest równoważne stwierdzeniu, że wymaga pełnej maszyny Turinga).

Tak więc, jeśli pomyślimy o lemacie pompowania dla języków regularnych , zasadniczo mówi on, że każdy język regularny można podzielić na trzy części, x , y i z , gdzie wszystkie wystąpienia języka znajdują się w xy * z (gdzie * jest powtórzeniem Kleene, tj. 0 lub więcej kopii y .) W zasadzie masz jeden „nieterminal”, który można rozwinąć.

A co z językami bezkontekstowymi? Istnieje analogiczny lemat o pompowaniu dla języków bezkontekstowych, który dzieli ciągi w języku na pięć części, uvxyz , i gdzie wszystkie wystąpienia języka są w uv ⁱ xy ⁱ z , dla i ≥ 0. Teraz masz dwa „nieterminale "które można powielić lub pompować, o ile masz ten sam numer .

Różnica między gramatyką regularną i bezkontekstową: (N, Σ, P, S): terminale, nieterminale, produkcje, stan początkowy Symbole terminali

● elementarne symbole języka określone przez gramatykę formalną

● abc

Symbole nieterminalne (lub zmienne składniowe)

● zastąpione grupami symboli terminali zgodnie z zasadami produkcji

● ABC

gramatyka regularna: prawa lub lewa gramatyka regularna prawa gramatyka regularna, wszystkie zasady są zgodne z formami

1. B → a, gdzie B jest nieterminalem w N, a a jest terminalem w Σ
2. B → aC, gdzie B i C są w N, a a jest w Σ
3. B → ε, gdzie B jest w N, a ε oznacza pusty łańcuch, czyli ciąg o długości 0

zostawił gramatykę regularną, wszystkie reguły są zgodne z formularzami

1. A → a, gdzie A jest nieterminalem w N, a a jest terminalem w Σ
2. A → Ba, gdzie A i B są w N, a a jest w Σ
3. A → ε, gdzie A jest w N, a ε jest łańcuchem pustym

gramatyka bezkontekstowa (CFG)

○ gramatyka formalna, w której każda reguła produkcji ma postać V → w

○ V jest pojedynczym nieterminalnym symbolem

○ w to ciąg terminali i / lub nieterminali (w może być puste)

Gramatyka regularna: - gramatyka zawierająca produkcję w następujący sposób to RG:

V->TV or VT
V->T

gdzie V = zmienna i T = terminal

RG może być lewą gramatyką liniową lub prawą gramatyką liniową, ale nie środkową gramatyką liniową.

Jak wiemy, wszystkie RG to Linear Grammar, ale tylko Left Linear lub Right Linear Grammar są RG.

Zwykła gramatyka może być niejednoznaczna.

S->aA|aB
A->a
B->a

Niejednoznaczna gramatyka: - dla łańcucha x istnieje więcej niż jeden LMD lub Więcej niż RMD lub Więcej niż jedno drzewo analizy lub Jedno LMD i jedno RMD, ale oba produkują różne drzewo analizy.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

ta Gramatyka jest niejednoznaczna Gramatyka, ponieważ dwa drzewa parsowania.

CFG: - gramatyka nazywana CFG, jeśli jej produkcja ma postać:

   V->@   where @ belongs to (V+T)*

DCFL: - jak wiemy, wszystkie DCFL to LL (1) Gramatyka, a wszystkie LL (1) to LR (1), więc nigdy nie jest niejednoznaczne. więc DCFG nigdy nie jest niejednoznaczne.

Wiemy również, że wszystkie RL to DCFL, więc RL nigdy nie jest niejednoznaczne. Zauważ, że RG może być niejednoznaczne, ale RL nie.

CFL: CFl Może być niejednoznaczny lub nie.

Uwaga: RL nigdy nie będzie z natury niejednoznaczne.

Wyrażenia regularne

• Podstawy analizy leksykalnej
• Reprezentuj języki regularne

Gramatyki bezkontekstowe

• Podstawy parsowania
• Reprezentuj konstrukcje językowe

Gramatyka jest bezkontekstowa, jeśli wszystkie reguły produkcji mają postać: A (to znaczy lewa strona reguły może być tylko pojedynczą zmienną; prawa strona jest nieograniczona i może być dowolną sekwencją terminali i zmiennych). Możemy zdefiniować gramatykę jako czteroosobową krotkę, gdzie V to skończony zbiór (zmienne), _ to skończony zbiór (terminale), S to zmienna początkowa, a R to skończony zbiór reguł, z których każda jest odwzorowaniem V
gramatyka regularna jest liniowa w prawo lub w lewo, podczas gdy gramatyka bezkontekstowa jest w zasadzie dowolną kombinacją terminali i nieterminali. stąd możemy powiedzieć, że gramatyka regularna jest podzbiorem gramatyki bezkontekstowej. Po tych właściwościach możemy powiedzieć, że zestaw języków wolnych od kontekstu zawiera również zestaw języków regularnych

Zasadniczo gramatyka regularna jest podzbiorem gramatyki bezkontekstowej, ale nie możemy powiedzieć, że każda gramatyka bezkontekstowa jest gramatyką regularną. Głównie gramatyka bezkontekstowa jest niejednoznaczna, a gramatyka regularna może być niejednoznaczna.

gramatyka regularna nigdy nie jest niejednoznaczna, ponieważ jest albo lewostronna, albo prawostronna, więc nie możemy utworzyć dwóch drzew decyzyjnych dla gramatyki regularnej, więc jest ona zawsze jednoznaczna. ale poza gramatyką regularną wszystkie mogą być regularne lub nie