a)
| <stmt> | ::= | <x-ing> | |
| <y-ing> | | ||
| epsilon | ||
| <x-ing> | ::= | x<some ys>x |
| <y-ing> | ::= | y<some xs>y |
| <some ys> | ::= | <some ys>y | |
| epsilon | ||
| <some xs> | ::= | <some xs>x | |
| epsilon |
b)
| <stmt> | ::= | <plus-before-dot> | |
| <plus-after-do> | ||
| <plus-before-dot> | ::= | <one-or-more><dot><zero-or-more> |
| <plus-after-dot> | ::= | <zero-or-more><dot><one-or-more> |
| <one-or-more> | ::= | <one-or-more><digit> | |
| <digit> | ||
| <zero-or-more> | ::= | <one-or-more> | |
| epsilon | ||
| <digit> | ::= | 0 | 1 |
| <dot> | ::= | . |
S produktionerne:
| S | ::= | S; S | |
| id := E | | ||
| print (L) |
For at eliminere venstre rekursion (left recursion) bruges omskrivning fra side 52 i bogen. S produktionerne opskrives som følgende, hvor S' er den nye non-terminal som indføres og <epsilon> er den tomme streng.
| S | ::= | id := E S' | |
| print (L) S' | ||
| S' | ::= | ;S S'| |
| <epsilon> |
Tilsvarende skal der elimineres venstre rekursion i E produktionerne
| E | ::= | id | |
| num | | ||
| E + E | | ||
| (S, E) |
omskrives som følger.
| E | ::= | id E'| |
| num E' | | ||
| (S, E) E' | ||
| E' | ::= | +E E'| |
| <epsilon> |
L produktionerne
| L | ::= | E |
| L, E |
| L | ::= | E L' |
| L' | ::= | ,E L' | |
| <epsilon> |
Det kan være nødvendigt at venstre fakturere (left factoring) en grammatik hvis den samme non-terminal har to produktioner, der starter med de samme symboler, se eksemplerne på slidene 25 og 26 fra gangen om "Syntax Analysis". I den omskrevne grammatik er der ikke brug for left factoring.
Det antages at \, { og } er terminaler. Når disse er terminaler er begin, end, og WORD ligeledes terminaler. Herudover anvender Appel her i dette eksempel at End-Of-File (EOF) skrives med ind i grammatikken som en terminal $. Bemærk at Appel's brug af om en non-terminal N er nullable svarer til at sige epsilon tilhører FIRST(N).
| Nullable | FIRST | FOLLOW | |
|---|---|---|---|
| S' | no | \, end, begin, WORD, {, $ | |
| S | yes | \, end, begin, WORD, { | \, $, } |
| X | no | \, end, begin, WORD, { | \, end, begin, WORD, { |
| B | no | \ | \, end, begin, WORD, {, $ |
| E | no | \ | \, end, begin, WORD, { |
a)
| <string> | ::= | <string> <terminal>| <terminal> |
| <terminal> | ::= | blank | tab | newline |
b)
| <sequence> | ::= | <letter><tail> |
| <tail> | ::= | <tail> <letter> | |
| <tail> <digit> | | ||
| epsilon | ||
| <letter> | ::= | a - z |
| <digit> | ::= | 0 - 9 |
c)
| <real> | ::= | <digit-star> <dot> <digit-plus> | |
| <digit-plus> <dot> <digit-star> | | ||
| <digit-plus> <dot> <digit-plus> | ||
| <digit-plus> | ::= | <digit-plus> <digit> | |
| <digit> | ||
| <digit-star> | ::= | <digit-plus> | |
| epsilon | ||
| <digit> | ::= | 0 - 9 |
| <dot> | ::= | . |
a) Listen indeholder en eller mange <name>s med komma mellem <name>s.
b) Listen indeholder en eller mange <field>s med semikolon efter hvert <field>
c) Listen indeholder nul eller mange <statement>s med semikolon mellem <statement>s
d) Listen indeholder en eller mange <factor>s med multiplikations tegnet mellem <factor>s
e) Listen indeholder nul eller en <variables>, som starter med var, hvis den er defineret. der er et kolon mellem <name list> og <type>. Herudover er <type> altid efterfulgt af et semicolon.
f) Listen indeholder nul eller flere <const-decls>s der hver starter med const og efter <name> og <constant> altid har et semicolon.
Venlig hilsen
Kristian Torp
torp (at) cs (dot) auc (dot) dk