代码之家 › 专栏 › 技术社区 › user8510613

如何在为RE(使用堆栈求值)构建语法树时处理隐式“cat”运算符

expression-evaluation recursive-descent grammar compiler-construction parsing

1

user8510613 · 技术社区 · 6 年前

我用不同类型的节点来表示不同类型的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操作员?我应该如何处理cat操作符,以正确地执行转换?

更新

现在我了解到有一种叫做“运算符优先文法”的文法,它的求值类似于算术表达式。它要求语法模式不能具有S->的形式。。。AB…(A和B是非终端)。所以我猜我不能直接使用这个方法来解析正则表达式。

更新II

我试图设计一个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' ,这是错误的。

那么,这个语法怎么了?我应该如何重写它,使之适合递归后代方法。

2 回复 | 直到 6 年前

1

2

Community CDub 4 年前

1.LL(1)语法

(a|b)

你已经到了这一步:

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

您有两种可能的产品:

T' â FT'
T' â Îµ

第一个(F)是 { ( , i } 因此,无论是对人类还是对人类来说,第一次生产显然是不正确的( 1. )解析器(没有前瞻性的解析器无法做出决定,但是没有前瞻性的解析器对于实际的解析几乎毫无用处。)

2.运算符优先解析

你技术上是对的。您的原始语法不是运算符语法。然而,用一个小的状态机扩充操作符优先解析器是正常的(否则,包括一元减号在内的代数表达式就不能被正确解析),一旦完成了,隐式连接操作符必须去哪里就很清楚了。

状态机在逻辑上相当于对输入进行预处理,以便在必要时插入显式连接运算符,即 a 和 b 无论何时 A. 在 { ), * , i } 和在 { ) , i}

您应该注意,除非您使用显式原语来表示空字符串,否则您的原始语法不会真正处理正则表达式。否则,您将无法表示可选的选项,这些选项通常在正则表达式中表示为隐式表达式 操作数 (例如 (a|) ,也常写成 a?

2

0

user2201041 user2201041 6 年前

我觉得只要跟踪上一个角色就足够了。所以如果我们有

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

我们知道 *

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

a 不是接线员, b 不是运算符,所以我们隐藏的运算符在它们之间。再一个:

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

| 是一个需要右操作数的二进制运算符,因此我们不进行串联。

完整的解决方案可能包括为每个可能的问题构建一个表 pc ,这听起来很痛苦,但它应该给你足够的背景,通过。

如果不想弄乱循环,可以进行预处理,使用类似的逻辑插入自己的连接字符。不能告诉你这是好是坏,但这是个主意。