Можем ли мы использовать DFA для анализа регулярного языка, заданного с помощью Context-Free Grammar, и генерации дерева синтаксического анализа?

Question

Как известно, DFA можно использовать для проверки строк на обычном языке.

Пример 1. L = ac (b) * bcb | ad (b) * bb. Строка «acbbbcb» может быть подтверждена DFA как правильная.

Также, иногда, регулярный язык может быть выражен CFG.

Пример 2.

• S -> "а" А "б"
• А -> "с" В "с" | "d" B
• B -> "b" B | «Б»

язык, порожденный выше CFG просто регулярное выражение в примере 1.

Это значит, мы можем использовать DFA для проверки (обычные) строки, генерируемые этой CFG. Однако как мы можем сгенерировать соответствующее дерево разбора?

Answer 1

Все обычные языки имеют CFG.

Поскольку DFA не имеет выхода за пределы accept/reject, он не может строго строить дерево разбора. Однако я не понимаю, почему нельзя было иметь по крайней мере некоторого DFA для каждого языка, который мог бы быть дополнен древовидными побочными эффектами (при условии, что грамматика недвусмысленная). Это, вероятно, требует, чтобы DFA был построен для отражения структуры грамматики и, следовательно, не обязательно минимален.

Если грамматика неоднозначна, то, как пишет Гюнтер, DFA, вероятно, недостаточно для целей деревообразования.

Answer 2

• S -> "а" А "б"
• А -> "с" B "с" | "d" B
• B -> "b" B | «Б»

Я думаю, что это может быть достигнуто следующим образом:

Представьте у вас есть несколько страниц бумаги. На каждой странице бумаги есть правило производства. И самая верхняя бумага имеет правило S -> "a" A "b". И есть два перехода: один из «А» на следующую страницу бумаги, а другой - со следующей страницы бумаги на этот «А».

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

Таким образом, DFA может генерировать дерево разбора. Однако этот DFA больше похож на «дерево» вместо «graph».

Эта схема может быть неполной. Если вы обнаружили какие-либо проблемы, сообщите мне.