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

Question

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

我使用不同类型的节点来表示不同类型的 RE。例如SymbolExpression、CatExpression、OrExpression和StarExpression，它们都是从正则表达式。

因此 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 运算符以正确实现转换？

更新

现在我知道有一种文法叫做“运算符优先文法”，它的求值类似于算术表达式。它要求文法的模式不能有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

1。 LL(1) 文法

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

(a|b)

你已经走到这一步了:

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

前瞻符号是|，你有两种可能的产生式:

T' ⇒ FT'
T' ⇒ ε

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

2。运算符优先级解析

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

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

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