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