0
Это было написано в книге ullmans, но я не стоял хорошо, как это работает. Может ли кто-нибудь объяснить даже в простом контексте? Я был бы очень рад.Какова связь между деревьями деривации и деривации?
A
ответ
1
Вывод - это последовательность, начинающаяся с символа начала S, заканчивается строкой на языке, а промежуточные этапы могут содержать терминалы и нетерминалы. Каждый шаг в последовательности расширяет один нетерминал с использованием правила производства.
Дерево разбора коренится на символ начала, имеет символы терминала в виде листьев, а дочерние узлы соответствуют правилу производства.
Например, с грамматикой S -> a | 1 | S + S, дифференцирование для a + a + 1 может быть
S -> S + S -> a + S -> a + S + S -> a + S + 1 -> a + a + 1
и соответствующее дерево разбора может быть
S
/| \
S + S
| /|\
a S + S
| |
a 1
Некоторые вопросы задавать на данный момент являются: Для данный язык или грамматика, имеет ли конкретная строка только одно дерево разбора? Только один вывод? Для конкретного вывода существует ли уникальное дерево разбора или наоборот?
+0
Большое вам спасибо! Это очень помогло мне! Я попытался перечитать книгу, и, наверное, я неправильно понял некоторые вещи. Но это дало мне простое представление о том, как это работает сейчас, еще раз спасибо так много :) – CSRivan
Можете ли вы включить более подробную информацию, например, например, пример деривации и дерева деривации? Вы имеете в виду конечные автоматы (как вы отметили это) или контекстно-свободные языки? –
жаль, что это часть моего предмета (автоматы). Я новичок в тегах, просто говоря о контекстном свободном языке/грамматике. Есть ли разница между этими двумя? – CSRivan
SO, похоже, использует конечные автоматы специально для обычных языков, поэтому я обновил здесь тег. –