Как отделить контекстно-свободную часть языка от контекстно-зависимой?

Я прочитал этот фантастический пост в списке comp.theory:

http://coding.derkeiler.com/Archive/General/comp.theory/2004-03/0189.html

Плакат подчеркивает, что большинство языков программирования определяют контекстно-свободное ядро, а затем имеют дополнительные алгоритмы, которые запускаются в дереве синтаксического анализа для фильтрации конструкций, недопустимых в языке:

Это отделяет контекстно-свободную часть языка от контекстно-зависимой, что обычно считается хорошей практикой (своего рода модульная дисциплина «программирование» для языкового дизайна).

Не могли бы вы привести пример «Hello World», чтобы проиллюстрировать эту технику? То есть предоставьте простой контекстно-зависимый язык, определите контекстно-свободное ядро, а затем набросайте, как анализировать ввод с помощью контекстно-свободного ядра, с последующей фильтрацией недопустимых конструкций в дереве синтаксического анализа.

Можете ли вы порекомендовать мне статьи или книги, в которых обсуждается эта техника?


language-design modularity context-free-grammar parse-tree context-sensitive-grammar
person Roger Costello    schedule 17.05.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Один из простейших языков, не зависящих от контекста, - это язык, в котором слова имеют тип a n b n c n (a, b и c повторяются одинаковое количество раз, то есть abc, aabbcc, aaabbbccc, ...).

Вы можете проанализировать его, используя грамматику для контекстно-свободного языка {a n b n c m}, где количество c не равно ограниченный. Получив дерево синтаксического анализа, вы проверяете с помощью отдельного алгоритма, что количество повторений c равно количеству повторений a и b.

person Joni    schedule 17.05.2013
comment
Этот ответ не о языках программирования, но вопрос был. - person Jurgen Vinju; 23.10.2013
comment
OP запросил пример простого контекстно-зависимого языка, который может быть проанализирован как контекстно-свободный язык плюс апостериорный проход фильтра. Ответ дает один. - person Joni; 23.10.2013

arrow_upward
0
arrow_downward

Как правило, фильтрация также выполняется для устранения неоднозначности приближения языков. Мы пишем неоднозначные, но понятные контекстно-свободные грамматики для языков программирования, а затем используем обходчики деревьев или другие механизмы для удаления нежелательных производных.

одна ссылка:

С другой стороны, вы также можете рассмотреть в качестве такого фильтра средство проверки типов, которое обрабатывает абстрактные синтаксические деревья. Средства проверки типов отклоняют деревья, созданные синтаксическим анализатором, на основе нелокальной (контекстной) информации. Например:

1 + "1"

принимается грамматикой, потому что:

E ::= Int | String | E "+" E;

но средство проверки типов говорит, что сложение не работает между целыми числами и строками, и отклоняет предложение из языка. Средство проверки типов делает это путем обхода дерева после анализа и идентификации символа добавления, затем, возможно, ищет допустимые комбинации операндов в таблице, и если комбинация недопустима, она начинает жаловаться. Я предполагаю, что обычно так работают компиляторы. См. Aho et al. книга дракона. Это звучит интереснее, если говорить об этом абстрактно :-)

person Jurgen Vinju    schedule 24.05.2013
comment
Язык, который вы используете в качестве примера, не зависит от контекста даже после проверки типа, поэтому на вопрос дан только частичный ответ. - person Joni; 23.10.2013
comment
Ты прав. Как вы думаете, стоит ли добавить более сложный пример? Решение, конечно, будет таким же. Что-то, что требует таблицы символов для устранения неоднозначности, или что-то с идентификатором, который необходимо объявить перед использованием, сделает это. - person Jurgen Vinju; 24.10.2013