Анализ рекурсивного спуска для логической грамматики

Question

Я пытаюсь изучать компиляторы и рекурсивный синтаксический анализ спуска на примере. Это не домашнее задание. Я попытался взглянуть на несколько других ответов, но мне трудно понять их.

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

Действительный синтаксис - это пробелы, круглые скобки, AND, OR и строчные слова. Строчные слова должны быть разделены булевыми операторами (т. Е. Cat AND mouse).

Некоторые примеры того, как это будет работать:

"cat AND mouse" = "cat <v>AND</v> mouse" 
"cat AND mouse OR" = "cat <v>AND</v> mouse <i>OR</i>" 
"pet OR ((domestic AND cat)" = "pet <v>OR</v> <i>(</i><v>(</v>domestic <v>AND</v> cat <v>)</v>" 
"cat food" = "cat <i>?</i> food" 

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

Я считаю, что грамматика языка выглядит следующим образом (пожалуйста, поправьте меня, если я ошибаюсь):

Expression -> 1 or more clauses 
Clause -> lowercase_term | (lowercase_term bool_op lowercase_term) 
Lowercase_Term -> 1 or more letters from [a-z] 
Bool_Op -> AND | OR 

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

Для справки, я делаю это на Java, но псевдокод или любой код языка, который поможет мне понять это, будет очень признателен!

Answer 1

Посмотрите на How To Build A Boolean Expression Evaluator - Using a recursive descent parser and the interpreter pattern. Это очень похоже на то, что вы просите.

Что касается определения «действительной» и «недопустимой» части ввода: простой подход: сначала попытайтесь разобрать полный текст. Если это работает, полный текст действителен. В противном случае проанализируйте текст до второго последнего символа и т. Д., Пока вы, наконец, не найдете префикс ввода, который действителен. Следующий текст после этого «недействителен».

Answer 2

Здесь вы можете прочитать и попробовать примеры, я объяснил там, как разобрать и интерпретировать арифметические выражения с использованием рекурсивного метод спуска разбора:

https://leanpub.com/pic/read#leanpub-auto-chapter-2---parsing-and-calculating-expressions

Рекурсивный спуск синтаксического анализа является -almost- наиболее интуитивный метод синтаксического анализа. Достаточно просто написать собственный интерпретатор с ручной кодировкой, а не только с помощью арифметических выражений, а также с циклами, инструкциями if-else и т. Д.

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

https://github.com/mehmetcoskun/contra

Это с открытым исходным кодом, вы можете скачать и настроить.