 |
|||
| HSG |
|
Gegeben ist die Grammatik
E → T | T + E T → F | F * T F → ( E ) | z
, dabei steht E für Expression, T für Term, F für Factor und z für eine Zahl. Wie üblich stehen Großbuchstaben für Non-Terminale, | ist ein Meta-Zeichen, + * ( ) sind literale Token. Es ist mit PLY ein Scanner und Parser zu bauen. Wir wollen das Programm zu Versuchszwecken benutzen. Dazu benötigen wir auch eine Darstellung in JFlap. Zunächst untersuchen wir die Abarbeitung von z+z*z.
Brute-Force-Parsing
ply-Scanner/Parser
import ply.lex as lex
tokens = ['z']
literals = '+*()'
def t_z(t):
r'\d+'
t.value = int(t.value)
return t
def t_newline(t):
r'\n+'
t.lexer.lineno = t.lexer.lineno + len(t.value)
t_ignore = ' \t'
def t_error(t):
print('Unerwartetes Zeichen:',t.value[0],',Zeile:',s.lineno)
t.lexer.skip(1)
s = lex.lex()
import ply.yacc as yacc
def p_0(p):
'E : T'
def p_1(p):
'E : T "+" E'
def p_2(p):
'T : F'
def p_3(p):
'T : F "*" T'
def p_4(p):
'F : "(" E ")"'
def p_5(p):
'F : z'
def p_error(p):
print('Syntaxfehler in Zeile:',s.lineno)
pr = yacc.yacc()
Fragen
- In welcher Reihenfolge werden die Produktionen verwendet?
- Kann man diese Reihenfolge zur Berechnung des Terms benutzen?
Aufgabe
Die Grammatik
A → A + A A → A - A A → z
erscheint einfach, birgt aber ein Problem. Teste mit JFlap, erstelle insbesondere zu z-z-z einen Brute-Force-Baum und einen SLR(1)-Baum. Was fällt auf? Welche Folgen hat das für die Berechnung? Wie verhält sich ply? ambi1.jff, ambi1.py
Welchen Weg geht ply, um das Problem zu lösen? Baue dein Programm entsprechend um und teste.
Links
- Ambiguous Grammar - wikipedia
- Dealing With Ambiguous Grammars - ply-Dokumentation