使这个表达式语法对于 LL(1) 来说是明确的

发布于 2025-01-08 08:54:51 字数 1160 浏览 2 评论 0原文

我们怎样才能使这个 Expression 语法对于 LL(1) 解析来说是明确的？

语法与大多数 C 类语言中使用的表达式非常相似。

注意：<>中的字符串是非终结符，而大写的则是终结符。

 <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 上找不到任何处理布尔表达式的问题。

原文

How can we make this Expression grammar unambiguous for LL(1) parsing?

The grammar is very similar to expressions used in most C like languages.

Note: Strings in <> are non-terminals, while those in Upper Case are terminals.

 <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: I coudn't find any question on Stackoverflow that handled Boolean Expressions.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

挥剑断情 2025-01-15 08:54:51

首先，您需要消除规则的歧义，

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

它应该如何处理像 a AND b OR c 和 a OR b AND c 这样的输入？有多种可能的解释；你需要决定你想要哪个。

然后，您将得到一个明确的语法，但不是 LL(1)。要使其为 LL(1)，您需要左因子它。

First you need to disambiguate the rule

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

How should it handle inputs like a AND b OR c and a OR b AND c? There are multiple possible interpretations; you need to decide which you want.

Then, you'll have a grammar that is unambiguous, but not LL(1). To make it LL(1) you need to left-factor it.

回复收藏 0 原文

梦纸 2025-01-15 08:54:51

@Chris，您的问题可能已纠正如下。然而完整语法的歧义并没有消失。
此外，标准形式的左因式分解在这里也是不可能的。

仅当我们尝试找到第一组时，我们才会得到左公因数（例如中的 BO）代码> 和 <代码><表达式>

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

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

@Chris, your issue is probably rectified as following. Yet ambiguity of the complete grammar does not vanish.
Also, left factoring in its standard form is not possible here.

We get left common factors (like BO in <booleanExpr>) only when we try to find the FIRST sets of <booleanExpr> and <expression>

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

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

回复收藏 0 原文

~没有更多了~