parsing - 解决语法问题的实用解决方案

Question

我们有一些非程序员编写的 vb6 代码片段(仅使用功能的子集)。这些被称为规则。对于编写这些的人来说，他们很难调试，所以有人写了一种附加的解析器来评估子表达式，从而更好地显示问题所在。

这个临时解析器非常糟糕，并且不能真正工作。所以我试图编写一个真正的解析器(因为我是手工编写的(没有解析器生成器我可以用 vb6 后端理解)我想使用递归体面的解析器)。我不得不对语法进行逆向工程，因为我可以找到任何东西。 (最终我发现了一些东西 http://www.notebar.com/GoldParserEngine.html 但它的 LALR 和它的方式比我需要的要大)

这是VB子集的语法。

<Rule>                 ::=  expr rule | e
<Expr>                 ::= ( expr )
                           | Not_List CompareExpr <and_or> expr
                           | Not_List CompareExpr

<and_or>                   ::= Or | And

<Not_List>             ::= Not Not_List | e

<CompareExpr>          ::= ConcatExpr comp CompareExpr
                           |ConcatExpr

<ConcatExpr>           ::= term  term_tail & ConcatExpr
                           |term term_tail

<term>                 ::= factor factor_tail
<term_tail>            ::= add_op term term_tail | e

<factor>               ::= add_op Value | Value
<factor_tail>          ::= multi_op  factor factor_tail | e

<Value>                ::= ConstExpr | function | expr

<ConstExpr>            ::= <bool> | number | string | Nothing
<bool>                 ::= True | False
<Nothing>              ::= Nothing | Null | Empty

<function>             ::= id | id ( ) | id ( arg_list )
<arg_list>             ::= expr , arg_list | expr

<add_op>               ::= + | -
<multi_op>             ::= * | /
<comp>                 ::= > | < | <= | => |  =< | >= |  = | <>

总而言之，它工作得很好，这里有一些简单的例子:

my_function(1, 2 , 3)  

好像

(Programm
 (rule
  (expr
   (Not_List)
   (CompareExpr
    (ConcatExpr
     (term
      (factor
       (value
        (function
         my_function
         (arg_list
          (expr
           (Not_List)
           (CompareExpr
            (ConcatExpr (term (factor (value 1))) (term_tail))))
          (arg_list
           (expr
            (Not_List)
            (CompareExpr
             (ConcatExpr (term (factor (value 2))) (term_tail))))
           (arg_list
            (expr
             (Not_List)
             (CompareExpr
              (ConcatExpr (term (factor (value 3))) (term_tail))))
            (arg_list))))))))
     (term_tail))))
  (rule)))

现在我的问题是什么？

如果你有这样的代码 (( true OR false ) AND true)我有一个无限递归，但真正的问题是在 (true OR false) AND true (在第一个 ( expr ) 之后)被理解为只有 (true or false) .

这是Parstree:


那么如何解决这个问题。我应该以某种方式更改语法还是使用一些实现技巧？

万一你需要它，一些很难的例子。

(( f1 OR f1 ) AND (( f3="ALL" OR f4="test" OR f5="ALL" OR f6="make" OR f9(1, 2) ) AND ( f7>1 OR f8>1 )) OR f8 <> "")

Answer 1

你有几个我看到的问题。

您将 OR 和 AND 视为同等优先级运算符。对于 OR 和 AND，您应该有单独的规则。否则，表达式 A OR B AND C 的优先级错误(因此计算)。

因此，作为第一步，我将修改您的规则如下:

<Expr>  ::= ( expr )                        
            | Not_List AndExpr Or  Expr   
            | Not_List AndExpr

<AndExpr>  ::=                        
            | CompareExpr And  AndExpr   
            | Not_List CompareExpr

下一个问题是您的列表顶层有 ( expr )。如果我写:

 A AND (B OR C)

要解决此问题，请更改以下两条规则:

<Expr>  ::= Not_List AndExpr Or Expr   
            | Not_List AndExpr

<Value> ::= ConstExpr | function | ( expr )

我认为您的 Not 实现不合适。不是运算符，
只有一个操作数，所以它的“树”应该有一个 Not 节点和一个子节点
是表达式 be Notted。你有一个没有操作数的 Not 列表。
试试这个:

<Expr>  ::= AndExpr Or Expr   
            | AndExpr

<Value> ::= ConstExpr | function | ( expr ) | Not Value

我没看过，但我认为VB6表达式中还有其他乱七八糟的东西。

如果您注意到，我编写的 Expr 和 AndExpr 的样式使用右递归来避免左递归。您应该更改 Concat、Sum 和 Factor 规则以遵循类似的风格；您所拥有的非常复杂且难以理解。