Vanlig grammatik

En vanlig grammatik  är en formell grammatik av typ 3 i Chomsky-hierarkin , reguljär grammatik definierar exakt alla reguljära språk , och är därför likvärdiga med tillståndsmaskiner och reguljära uttryck . Vanliga grammatiker är en delmängd av sammanhangsfria grammatiker .

Ange en uppsättning regler

En vanlig grammatik kan specificeras av en uppsättning regler som en vänster eller höger vanlig grammatik.

Rätt reguljär grammatik , eller högerlinjär grammatik , - alla regler kan ha någon av följande former:

1. A → a
2. A → aB
3. A →ε

vänster reguljär grammatik , eller vänsterlinjär grammatik , - alla regler kan ha någon av följande former:

1. A → a
2. A → Ba
3. A →ε

var

• versaler ( A , B ) anger icke-terminaler från mängden N
• Små bokstäver ( a , b ) anger terminaler från mängden Σ
• ε är en tom sträng, dvs en sträng med längden 0

Klasserna av höger och vänster reguljär grammatik är likvärdiga - var och en för sig räcker för att definiera alla reguljära språk. Vilken vanlig grammatik som helst kan konverteras från vänster till höger och vice versa.

De alternativa namnen beror på att de är underklasser till den mer allmänna klassen av linjär grammatik .

Exempel

Den rätta reguljära grammatiken G som ges av N = {S, A}, Σ = {a, b, c}, P består av följande regler:

och S är startsymbolen. Denna grammatik beskriver samma språk som det reguljära uttrycket a*bc*.

Begränsad

Det är väsentligt att reglerna antingen endast är vänster-reguljära eller endast höger-reguljära. En kombination av båda är inte tillåten. Till exempel, ett sammanhangsfritt strängspråk av formen , där är inte regelbundet, utan ges av en grammatik G , där N = {S, A}, Σ = {a, b}, P består av

och S är startsymbolen. Denna grammatik innehåller både vänster-reguljära och höger-reguljära regler, och är därför inte regelbunden.

Se även

• Reguljära uttryck - i teorin om formella språk
• Prefix grammatik

Litteratur

• Robin Hunter. Grundläggande kompilatorkoncept = essensen av kompilatorer. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
• Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori och implementering av programmeringsspråk  - M.: MZ-Press, 2006, 2nd ed. — ISBN 5-94073-094-9