Практическое решение для устранения проблемы грамматики - PullRequest
Новая
       43

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

3 голосов
/ 08 июля 2011

У нас есть небольшие фрагменты кода 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: Parse Tree

Так как это решить.Должен ли я как-то изменить грамматику или использовать какой-нибудь хакерский имплментатор?

Что-то сложное, например, на случай, если оно вам понадобится. 

(( 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 ]

1 голос
/ 08 июля 2011

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

Вы рассматриваете 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 является оператором, только с одним операндом, поэтому его "дерево" должно иметь узел Not и дочерний элемент, который является выражением Notted.Что у вас есть список Nots без операндов.Попробуйте вместо этого: 

<Expr>  ::= AndExpr Or Expr   
            | AndExpr

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

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

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

0 голосов
/ 09 июля 2011

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

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

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

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

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

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

...