Можем ли мы использовать DFA для синтаксического анализа обычного языка, указанного контекстно-свободной грамматикой, и создания дерева синтаксического анализа?

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

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

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

Пример 2.

  • S -> "a" A "b"
  • A -> "c" B "c" | "d" B
  • B -> "b" B | "b"

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

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


regex dfa regular-language context-free-grammar parse-tree
person JackWM    schedule 09.05.2012    source источник
comment
Это не ответ на ваш вопрос, но некоторое время назад я нашел онлайн-визуализатор регулярных выражений: regexvisualizer.apphb.com< /а>   -  person Hauns TM    schedule 25.05.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

person ibid    schedule 09.05.2012
comment
Привет, там же, я думаю, что ваша точка зрения о том, что для этого требуется, чтобы DFA был построен с отражением правил производства грамматики, верна и важна. - person JackWM; 25.05.2012

arrow_upward
0
arrow_downward

  • S -> "a" A "b"
  • A -> "c" B "c" | "d" B
  • B -> "b" B | "b"

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

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

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

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

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

person JackWM    schedule 24.05.2012