Какой класс языков можно проанализировать с помощью yacc?

Question

Я недавно узнал, что C не имеет контекстно-свободной грамматики .Я также недавно узнал, что gcc использовал yacc для разбора C .Руководство для утилиты yacc гласит «Класс спецификаций, принятых [by yacc], является очень общим: грамматики LALR (1) с правилами устранения неоднозначности» , в то время как Википедия заявляет , чтоLALR грамматики являются подмножеством детерминированных контекстно-свободных грамматик, которые являются подмножеством контекстно-свободных грамматик.Если C даже не является контекстно-свободным (гораздо менее детерминированным контекстно-свободным языком), и все же yacc может анализировать C, то какой класс языков может анализировать yacc, если не подмножество контекстно-свободных языков, имеющих LALR (1)грамматик

Answer 1

Yacc генерирует компьютерные программы, которые довольно хорошо завершены.Фреймворк yacc использует фреймворк LALR (1) для запуска действий, но действия представляют собой произвольный код.

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

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

ВКороче говоря, реальные парсеры - это прагматически написанные программы, а не теоретические академические упражнения.Языки, анализируемые с помощью bison / yacc, обычно «в основном» LALR (1), и их лексический анализ обычно «в основном» регулярен, но не удивляйтесь, когда компьютерные программы используют всю свою мощь для преодоления этих ограничений.

Вот что делает программирование интересным занятием.

Ничто из этого не делает академическую теорию менее полезной.Bison / yacc и другие генераторы синтаксических анализаторов берут на себя большую часть тяжелой работы по созданию синтаксических анализаторов, потому что они могут обрабатывать «большую часть» анализа.И чем ближе язык подходит к анализируемой модели без контекста, тем легче создавать («большинство») другие полезные инструменты: линтеры, подсветки синтаксиса, переформаторы, индексаторы, статические анализаторы, экстракторы документации и т. Д. И т. Д. И т. Д.Не говоря уже о функционировании в качестве документации для синтаксиса самого языка.

Answer 2

C не имеет контекстно-свободной грамматики только по тривиальной причине, что семантическая классификация идентификатора токена (его лексическая категория) иногда требует понимания, как он объявлен.C предназначен для компиляции за один проход, поэтому в любой момент синтаксического анализа все, что имеет отношение к синтаксическому анализу, известно из предыдущих объявлений.Объявления в области видимости могут использоваться для назначения лексической категории токену.

Так, например, если синтаксический анализатор обращен к (A)(B) в середине блока оператора, это может быть:

• выражение (B) приводится к типу A.

• список аргументов (B) применяется к выражению функции (A).

Но эта двусмысленность не должна возникать в синтаксическом анализаторе, потому что лексический анализатор может заглянуть в область видимости и классифицировать A по-разному в зависимости от того, является ли это typedef именем или чем-то еще,и на эти по-разному классифицированные идентификаторы могут быть нацелены отдельные грамматические правила.Это похоже на магического оракула, который помечает токены семантической информацией, поэтому можно применять метод без контекста.

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