如何在为 RE 构建语法树时处理隐式 'cat' 运算符（使用堆栈评估）

Question

我正在尝试为正则表达式构建语法树。我使用类似算术表达式求值的策略（我知道有递归下降之类的方法），即使用两个堆栈，OPND堆栈和OPTR堆栈，然后处理。

我使用不同类型的节点来表示不同类型的 RE。比如SymbolExpression、CatExpression、OrExpression、StarExpression，都是从RegularExpression.

派生出来的

因此 OPND 堆栈存储 RegularExpression*。

while(c || optr.top()):
    if(!isOp(c):
        opnd.push(c)
        c = getchar();
    else:
        switch(precede(optr.top(), c){
        case Less:
          optr.push(c)
          c = getchar();
        case Equal:
          optr.pop()
          c = getchar();
        case Greater:
          pop from opnd and optr then do operation, 
          then push the result back to opnd
        }

但我的主要问题是，在典型的 RE 中，cat 运算符是隐式的。 a|bc代表a|b.c，(a|b)*abb代表(a|b)*.a.b.b。那么在遇到非接线员时，如何判断是否有猫接线员呢？我应该如何处理 cat 运算符以正确实现转换？

更新

现在我知道有一种文法叫做"operator precedence grammar"，它的求值类似于算术表达式。它要求文法的模式不能有S -> ...AB...的形式（A和B是非终结符）。所以我想我不能直接使用这种方法来解析正则表达式。

更新二

我尝试设计一个LL(1)文法来解析基本的正则表达式。这是原始语法。（\|是转义字符，因为 |是语法模式中的特殊字符)

E -> E \| T | T
T -> TF | F
F -> P* | P
P -> (E) | i

要删除左递归，导入新变量

E -> TE'
E' -> \| TE' | ε
T -> FT'
T' -> FT' | ε
F -> P* | P   
P -> (E) | i

现在，对于模式 F -> P* | P，导入P'

P' -> * | ε
F -> PP'

但是，模式 T' -> FT' | ε 有问题。考虑案例 (a|b)：

E => TE' 
  => FT' E'
  => PT' E'
  => (E)T' E'
  => (TE')T'E'
  => (FT'E')T'E'
  => (PT'E')T'E'
  => (iT'E')T'E'
  => (iFT'E')T'E'

在这里，我们的人类知道我们应该用 T' -> ε 替换变量 T'，但是程序只会调用 T' -> FT'，这是错误的。

那么，这个语法有什么问题？我应该如何重写它以使其适合递归派生方法。

Answer 1

我认为只要记住前一个字符就足够了。所以如果我们有

(a|b)*abb
      ^--- we are here
c = a
pc = *

我们知道*是一元的，所以'a'不能作为它的操作数。所以我们必须有连接。同样在下一步

(a|b)*abb
       ^--- we are here
c = b
pc = a

a 不是运算符，b 不是运算符，所以我们的隐藏运算符介于它们之间。再来一张：

(a|b)*abb
   ^--- we are here
c = b
pc = |

| 是一个需要右手操作数的二元运算符，所以我们不连接。

完整的解决方案可能涉及为每个可能的 pc 构建一个 table，这听起来很痛苦，但它应该为您提供足够的上下文来解决问题。

如果您不想弄乱循环，可以执行预处理过程，在其中使用类似的逻辑插入您自己的连接字符。不能告诉你这是好是坏，但这是一个想法。

Answer 2

1。 LL(1) 文法

我没有发现您的 LL(1) 语法有任何问题。您正在解析字符串

(a|b)

你已经走到这一步了：

(a   T'E')T'E'   |b)

前瞻符号是 | 并且您有两种可能的产生式：

T' ⇒ FT'
T' ⇒ ε

FIRST(F)是{<kbd>(</kbd>,<kbd>i</kbd>},所以第一个产生式对于人类和 LL(1) 解析器来说显然是不正确的。（没有前瞻的解析器无法做出决定，但没有前瞻的解析器对于实际解析几乎没有用。）

2。运算符优先级解析

你在技术上是正确的。您的原始语法不是运算符语法。然而，用一个小的状态机来增加运算符优先级解析器是很正常的（否则代数表达式包括一元减号，例如，不能被正确解析），一旦你这样做了，隐式连接运算符必须去哪里就很清楚了。

状态机在逻辑上等效于预处理输入以在必要时插入显式连接运算符——也就是说，只要 a 在 [=] 中，就在 a 和 b 之间40=]{), *, i} 和 b 在 {<kbd>)</kbd>, i</kbd>}.

您应该注意，您的原始语法并不真正处理正则表达式，除非您使用显式 ε 基元来扩充它来表示空字符串。否则，你没有办法表达可选的选择，通常在正则表达式中表示为隐含的操作数（如(a|)，也常写成a?）。但是，状态机也很容易检测隐式操作数，因为隐式连接和隐式 epsilon 之间在实践中没有冲突。

如何在为 RE 构建语法树时处理隐式 'cat' 运算符（使用堆栈评估）

How to deal with the implicit 'cat' operator while building a syntax tree for RE(use stack evaluation)

compiler-construction

grammar

parsing

recursive-descent

expression-evaluation

更新

更新二

1。 LL(1) 文法

2。运算符优先级解析