Парсер комбинатор для логики высказываний - PullRequest
Новая
       54

Парсер комбинатор для логики высказываний

0 голосов
/ 26 июня 2019

Я бы хотел создать комбинатор для анализа логики высказываний. Вот простой БНФ : 

<sentence> ::= <atomic-sentence> | <complex-sentence>
<atomic-sentence> ::= True | False | P | Q | R
<complex-sentence> ::= (<sentence>)
                       | <sentence> <connective> <sentence>
                       | ¬<sentence>
<connective> ::= ∧ | ∨ | ⇒ | ⇔

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

P∧Q

Есть ли простой способ исправить грамматику так, чтобы она подходила для комбинатора синтаксического анализа? Спасибо.

FWIW, я использую FParsec в F #, но я думаю, что любая библиотека комбинатора синтаксического анализатора будет иметь такую ​​же проблему.

1 Ответ

1 голос
/ 27 июня 2019

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

Комбинаторы парсеров, как правило, не поддерживают левую рекурсию, но они, как правило, поддерживают повторение.К счастью, леворекурсивное правило в форме <a> ::= <a> <b> | <c> можно переписать с помощью оператора повторения * в <a> ::= <c> <b>*.Если затем вы сложите левый список полученного списка, вы можете построить дерево, которое будет выглядеть так же, как дерево разбора, которое вы получили бы из исходной грамматики.

Так что, если мы сначала встроим <complex-sentence> в <sentence> и затем примените вышеуказанный шаблон, мы получим <a> = <sentence>, <b> = <connective> <sentence> и <c> = <atomic-sentence> | '(' <sentence> ')' | ¬<sentence>, что приведет к следующему правилу после преобразования: 

<sentence> ::= ( <atomic-sentence>
               | '(' <sentence> ')'
               | ¬<sentence>
               )* <connective> <sentence>

Чтобы улучшить читаемость, мы поставим круглые скобкичасть в собственном правиле: 

<operand>  ::= <atomic-sentence>
             | '(' <sentence ')'
             | ¬<sentence>
<sentence> ::= <operand> (<connective> <sentence>)*

Теперь, если вы попробуете эту грамматику, вы заметите нечто странное: список, созданный *, будет содержать только один элемент (или ни одного).Это потому, что если имеется более двух операндов, рекурсивный вызов <sentence> сожрет все операнды, создавая правоассоциативное дерево разбора.

Так что на самом деле приведенная выше грамматика эквивалентна этому (илискорее грамматика неоднозначна, но комбинатор синтаксического анализатора будет обрабатывать ее так, как если бы она была эквивалентна этому: 

<sentence> ::= <operand> <connective> <sentence>

Это произошло потому, что исходная грамматика была неоднозначной.Неоднозначное определение <s> ::= <s> <c> <s> | <o> может быть истолковано как леворекурсивное <s> ::= <s> <c> <o> | <o> (которое создаст левоассоциативное дерево разбора) или праворекурсивное <s> ::= <o> <c> <s> | <o> (правоассоциативное дерево разбора).Поэтому сначала следует устранить неоднозначность, выбрав одну из этих форм, а затем применить преобразование, если применимо.

Поэтому, если мы выберем леворекурсивную форму, мы получим: 

<sentence> ::= <operand> (<connective> <operand>)*

Который действительно будет создавать списки с более чем одним элементом.В качестве альтернативы, если мы выберем праворекурсивное правило, мы можем просто оставить его как есть (без оператора повтора), так как для устранения нет левой рекурсии.

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

Чтобы исправить приоритет, вы можете применить к списку что-то вроде алгоритма маневрового двора или сначалаПерепишите грамматику, чтобы учесть приоритет, а затем примените преобразование.

...