3

注意：这是递归下降优先级解析缺少前缀表达式的更详细版本

我正在构建一个简单的语言解析器，并且遇到了较低优先级前缀表达式的问题。这是一个示例语法：

E = E8
E8 = E7 'OR' E8 | E7
E7 = E6 'XOR' E7 | E6
E6 = E5 'AND' E6 | E5
E5 = 'NOT' E5 | E4
E4 = E3 '==' E4 | E3 '!=' E4 | E3
E3 = E2 '<' E3 | E2 '>' E3 | E2
E2 = E1 '+' E2 | E1 '-' E2 | E1 '*' E2 | E1 '+' E2 | E1
E1 = '(' E ')' | 'true' | 'false' | '0'..'9'

但是，如果它用作更高优先级中缀运算符的 RHS，则此语法不适用于 NOT，即：

true == NOT false

这是由于 RHS 上需要 == 运算符E3，它不能是“NOT”操作。

我不确定表达这种语法的正确方法？是否仍然可以使用这种简单的递归下降方法，或者我需要转向更具特色的算法（调车场或优先攀登）。

以下是一些需要正确解析的示例：

  • 输入true == 1 < 2,输出==(true, <(1, 2))
  • 输入1 < 2 == true,输出==(<(1, 2), true)
  • 输入NOT true == false,输出NOT(==(true, false))
  • 输入true == NOT false，输出==(true, NOT(false))**不起作用
  • 输入true < NOT false，输出<(true, NOT(false))**不起作用

我已尝试更改级别E4, E3, 并在中缀表达式的 RHS 上E2使用，如递归下降优先级解析缺少的前缀表达式（即,等）中所建议的那样。然而，这打破了这些级别之间的优先级，即错误地<(==(true, 1), 2)`。E5E3 '==' E5E3 '<' E5true == 1 < 2parsed as

4

1 回答 1

0

当坚持你的语言被定义的方式时，你不能

true == NOT false

作为您的语言中的有效术语。因为那时

NOT false == true

将是模棱两可的：解析树可以是

    NOT
     | 
    ==
   /  \
false true

或者

   ==
  /  \
 NOT true
  |
false

注意

true == NOT (false)

是您的语言中的有效术语。您的语言的一个可能更直观的定义是将NOT-level 从E5down 放到E2. 然后

true == NOT false 
NOT false == true

都有效并NOT与false. 第二个表达式的替代含义将表示为

NOT (false == true)

如果这些选项仍然不能满足您，您必须更改/扩展工具。例如，yacc/bison 解析器允许明确定义运算符优先级；参见例如这里

于 2014-06-21T21:08:54.500 回答