Практическое решение проблемы грамматики

У нас есть небольшие фрагменты кода vb6 (единственное использование подмножества функций), который запрограммирован не программистами. Это так называемые правила. Людям, пишущим их, их сложно отлаживать, поэтому кто-то написал своего рода анализатор add hoc, чтобы иметь возможность оценить подвыражения и тем самым лучше показать, где проблема.

Этот синтаксический анализатор addhoc очень плох и на самом деле не работает. Поэтому я пытаюсь написать настоящий парсер (потому что я пишу его вручную (без генератора парсеров, который я мог бы понять с помощью бэкэндов 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 <> "")
Источник

2 ответа

Решение

У меня есть несколько проблем, которые я вижу.

Вы рассматриваете OR и AND как операторы равного приоритета. У вас должны быть отдельные правила для ИЛИ и для И. В противном случае вы получите неправильный приоритет (следовательно, оценку) для выражения A ИЛИ B И 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 и дочерний элемент, который является выражением Notted. Что у вас есть список Nots без операндов. Попробуйте это вместо этого:

<Expr>  ::= AndExpr Or Expr   
            | AndExpr

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

Я не смотрел, но я думаю, что выражения VB6 содержат другие грязные вещи в них.

Если вы заметили, стиль Expr и AndExpr, который я написал, использует правую рекурсию, чтобы избежать левой рекурсии. Вы должны изменить свои правила Concat, Sum и Factor, чтобы следовать схожему стилю; то, что у вас есть, довольно сложно и трудно понять.

Источник

Если они просто создают фрагменты, то, возможно, VB5 "достаточно хорош" для их создания. И если VB5 достаточно хорош, возможно, стоит найти бесплатное VB5 Control Creation Edition:

http://www.thevbzone.com/vbcce.htm

Вы можете сделать так, чтобы они начали с проекта "Test Harness", к которому они добавляют фрагменты, и они могут даже протестировать их.

С небольшой ориентацией это, вероятно, окажется гораздо более практичным, чем создание синтаксического анализатора вручную, и намного более полезным, поскольку они могут проверять не только правильный синтаксис.

Если VB5 не хватает, вы можете включить статический модуль в "тестовый комплект", который обеспечивает грубый и готовый эквивалент Split(), Replace() и т. Д.

http://support.microsoft.com/kb/188007

Источник
Другие вопросы по тегам