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

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

Этот парсер 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

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

Что-то сложное exmplale в случае, если вам это нужно.

(( 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 <> "")

nickik 08.07.2011 источник

comment

Вероятно, вам следует прочитать ответы на три других вопроса на SO с тегом left-recursion. - Karl Knechtel 08.07.2011

comment

VB6 трудно анализировать, в основном из-за плохой документации, а также из-за странностей во взаимодействии между операторами внутри строк и операторами, которые охватывают строки. Существуют надежные парсеры VB6. См. парсер моей компании: semanticdesigns.com/Products/FrontEnds/VisualBasicFrontEnd.html - Ira Baxter 08.07.2011

Ответы (2)

arrow_upward
1
arrow_downward

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

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

<Expr>  ::= AndExpr Or Expr   
            | AndExpr

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

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

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

Ira Baxter 08.07.2011

arrow_upward
0
arrow_downward

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

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

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

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

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

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

Bob77 09.07.2011

comment

VB5CCE может даже принимать надстройки IDE, такие как MZ-Tools 3.0, и, в конце концов, вы можете сделать этих людей намного более продуктивными. - Bob77; 09.07.2011

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

Ответы (2)

Вопросы по теме