Сделайте эту грамматику выражения однозначной для LL (1)

Question

Как мы можем сделать это выражение грамматикой однозначным для анализа LL (1)?

Грамматика очень похожа на выражения, используемые в большинстве языков, подобных Си.

Примечание: строки в <> не являются терминалами, а строки в верхнем регистре являются терминалами.

---

 <expression> -->  <arithmeticExpr> | <booleanExpr>

 <arithmeticExpr> -->  <arithmeticExpr> <op1> <term> | <term> 

 <term> -->  <term> <op2> <factor> 
 <term> -->  <factor>

 <factor> -->  BO <arithmeticExpr> BC 
 <factor> -->  <var> 

 <op1> -->  PLUS | MINUS

 <op2> -->  MUL | DIV  

 <booleanExpr> -->  <booleanExpr> <logicalOp> <booleanExpr> 
 <booleanExpr> -->  <arithmeticExpr> <relationalOp> <arithmeticExpr> 
 <booleanExpr> -->   BO <booleanExpr> BC

 <logicalOp> -->  AND | OR 

 <relationalOp> -->   LT | LE | GT | GE | EQ | NE

 <var> --> ID <whichId> | NUM | RNUM 

 <whichId> --> SQBO ID SQBC | ε

---

PS: Я не нашел ни одного вопроса по Stackoverflow, который обрабатывал Boolean Expressions.

Answer 1

Сначала вам нужно устранить неоднозначность правила

<booleanExpr> -->  <booleanExpr> <logicalOp> <booleanExpr>

Как оно должно обрабатывать вводы, такие как a AND b OR c и a OR b AND c?Есть несколько возможных интерпретаций;вам нужно решить, какой вы хотите.

Тогда у вас будет однозначная грамматика, но не LL (1).Чтобы сделать его LL (1), вам нужно с левым коэффициентом it.

Answer 2

@ Крис, ваша проблема, вероятно, исправлена ​​следующим образом. Однако двусмысленность полной грамматики не исчезает.
Кроме того, левый факторинг в его стандартном виде здесь невозможен.
Мы получаем левые общие факторы (например, BO в <booleanExpr>) только тогда, когда мы пытаемся найти ПЕРВЫЕ наборы <booleanExpr> и <expression>

---

<booleanExpr> -->  <arithmeticExpr> <relationalOp> <arithmeticExpr> <BooleanX>
<booleanExpr> -->   BO <booleanExpr> BC <BooleanX>

<BooleanX> -->  <logicalOp> <booleanExpr> <BooleanX> | ε