summaryrefslogtreecommitdiff
path: root/grammar-ll1.txt
diff options
context:
space:
mode:
authorPeter Wu <peter@lekensteyn.nl>2016-05-08 12:19:01 +0200
committerPeter Wu <peter@lekensteyn.nl>2016-05-08 12:19:01 +0200
commit4dbbdbab2dbdd265e2c06db02823c29c236e91dd (patch)
tree3b6ed6e4f8e1cb952aa1b8badf4140a98fc52186 /grammar-ll1.txt
parentb42098ef8cc477459d1926bf08bd8400c6ecbfea (diff)
downloadRegexTest-4dbbdbab2dbdd265e2c06db02823c29c236e91dd.tar.gz
grammar-l11: remove left-recursion
In the original change, the EXP in PROD-EXP should have been PROD-EXP, similarly EXP in SINGLE-EXP should have been SINGLE-EXP. Otherwise the operator precedence is not applied correctly (consider 1+2*3, it should be interpreted as 1+(2*3), not (1+2)*3). Anyway, this change removes left-recursion as described in 2.12.1.
Diffstat (limited to 'grammar-ll1.txt')
-rw-r--r--grammar-ll1.txt18
1 files changed, 10 insertions, 8 deletions
diff --git a/grammar-ll1.txt b/grammar-ll1.txt
index 23c1abf..4e97893 100644
--- a/grammar-ll1.txt
+++ b/grammar-ll1.txt
@@ -12,14 +12,16 @@ context-free syntax
STATEMENT ::= ID ":=" EXP
context-free syntax
- 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 ")"
+ EXP ::= PROD-EXP PLUS-EXP'
+ PLUS-EXP' ::= "+" PROD-EXP PLUS-EXP'
+ PLUS-EXP' ::=
+ PROD-EXP ::= SINGLE-EXP PROD-EXP'
+ PROD-EXP' ::= "*" SINGLE-EXP PROD-EXP'
+ PROD-EXP' ::=
+ SINGLE-EXP ::= "-" SINGLE-EXP
+ SINGLE-EXP ::= ID
+ SINGLE-EXP ::= NAT
+ SINGLE-EXP ::= "(" EXP ")"
lexical syntax
ID ::= [a-z] ID'