summaryrefslogtreecommitdiff
path: root/grammar-ll1.txt
diff options
context:
space:
mode:
authorPeter Wu <peter@lekensteyn.nl>2016-05-07 20:04:10 +0200
committerPeter Wu <peter@lekensteyn.nl>2016-05-07 20:04:10 +0200
commitb42098ef8cc477459d1926bf08bd8400c6ecbfea (patch)
tree5fd7368d75afbf50357aba21ae3bce678d5656f4 /grammar-ll1.txt
parent1505dd49aec92d98d7226d970b1ccd9420558ebf (diff)
downloadRegexTest-b42098ef8cc477459d1926bf08bd8400c6ecbfea.tar.gz
Attempt to convert grammar to LL(1)
Needs more verification, but the idea is that the expressions with lowest precedence (+) should be the first one in the parse tree (implying that non-terminals with highest precedence should be just above a terminal). Left-associativity is achieved by the trick in section 2.3.1 of Intro2CD which results in the left operand being recursed instead of the right one.
Diffstat (limited to 'grammar-ll1.txt')
-rw-r--r--grammar-ll1.txt19
1 files changed, 8 insertions, 11 deletions
diff --git a/grammar-ll1.txt b/grammar-ll1.txt
index 9487bd1..23c1abf 100644
--- a/grammar-ll1.txt
+++ b/grammar-ll1.txt
@@ -12,12 +12,14 @@ context-free syntax
STATEMENT ::= ID ":=" EXP
context-free syntax
- EXP ::= ID
- EXP ::= NAT
- EXP ::= EXP "+" EXP {left}
- EXP ::= EXP "*" EXP {left}
- EXP ::= "-" EXP
- EXP ::= "(" EXP ")"
+ EXP ::= EXP "+" PROD-EXP
+ EXP ::= PROD-EXP
+ PROD-EXP ::= EXP "*" SINGLE-EXP
+ PROD-EXP ::= SINGLE-EXP
+ SINGLE-EXP ::= "-" EXP
+ SINGLE-EXP ::= ID
+ SINGLE-EXP ::= NAT
+ SINGLE-EXP ::= "(" EXP ")"
lexical syntax
ID ::= [a-z] ID'
@@ -34,8 +36,3 @@ lexical syntax
LAYOUT ::= " " LAYOUT
LAYOUT ::= "\n" LAYOUT
LAYOUT ::=
-
-context-free priorities
- EXP ::= "-" EXP >
- EXP ::= EXP "*" EXP >
- EXP ::= EXP "+" EXP