From 4dbbdbab2dbdd265e2c06db02823c29c236e91dd Mon Sep 17 00:00:00 2001
From: Peter Wu
Date: Sun, 8 May 2016 12:19:01 +0200
Subject: 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.
---
grammar-ll1.txt | 18 ++++++++++--------
1 file 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'
--
cgit v1.2.1