Какие современные компьютерные языки относятся к LL(1)?

Думаю, у меня возникнет соблазн пометить эту цитату из Википедии с помощью [необходима цитата]; предположения, по крайней мере, сомнительны. Например, существует большое количество инструментов для создания компиляторов на основе yacc, которые чрезвычайно упрощают , на практике для создания синтаксического анализатора с использованием более мощного (и такого же быстрого) алгоритма LALR, а некоторые также реализуют еще более мощный (и почти такой же быстрый в большинстве практических грамматик) алгоритм GLR. Синтаксические анализаторы рукописного ввода не были нужны десятилетиями. [Примечание 1]

Пытаясь ответить на вопрос:

1. Большинство компьютерных языков «технически» не являются LL, потому что они даже не являются контекстно-свободными. Сюда входят языки, требующие объявления идентификаторов (C, C++, C#, Java и т. д.), а также языки с препроцессорами и/или средствами макросов (среди прочих, C и C++), языки с неоднозначностями, которые могут быть только решена с использованием семантической информации (Perl был бы худшим преступником здесь, но C и C++ также находятся на первом месте). И, чтобы еще больше развеселить окружающих, он также включает в себя языки, поддерживающие компоновку наподобие Python (разумеется, Python, а также Haskell).

   Я ставлю пугающие кавычки вокруг «технически», потому что есть много людей, которые скажут, что эти исключения «не считаются». Это их мнение, и они имеют на него право (во всяком случае, я перестал с этим спорить, хотя и не разделяю этого мнения). Вы можете, например, исключить препроцессор из C/C++, предварительно обработав текст перед применением грамматики, или предварительно обработать языки, поддерживающие пробелы, вставив токены INDENT, NEWLINE и DEDENT вместо пробела, после чего вы можете сделать какое-то утверждение. о мистическом «основном языке». (Это гораздо сложнее применить к шаблонам C++, которые можно устранить только путем синтаксического анализа текста, поэтому вы не можете утверждать, что расширение может быть выполнено до синтаксического анализа.)

   Утверждение, что язык не является контекстно-свободным, поскольку требует объявления идентификаторов, возможно, немного более спорно. В некоторых языках (кроме C/C++, в которых требуется семантический анализ, чтобы избежать двусмысленности) вы можете утверждать, что дерево синтаксического анализа может быть построено без проверки правила объявления, что делает это правило «несинтаксическим». Но остается тот случай, когда вы можете применять правило объявления синтаксически; вы просто не можете сделать это с помощью контекстно-свободной грамматики (вы можете использовать грамматику Ван Вейнгардена, для пример).

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

2. Цель синтаксического анализа состоит в том, чтобы создать синтаксическое дерево, а не только в том, чтобы распознать, является ли текст допустимым или нет. (Вы можете упустить этот важный факт, если бегло пролистнете учебники по формальным языкам, которые, как правило, сосредоточены на распознавании, возможно, потому, что построение синтаксических деревьев менее интересно.) Таким образом, кажется разумным настаивать на том, что предлагаемая грамматика действительно представляет синтаксическую структуру языка.

   Например, вы можете распознавать алгебраические выражения, используя простой обычный язык:

   (PREFIX* OPERAND POSTFIX*) (INFIX PREFIX* OPERAND POSTFIX*)*
   

   где PREFIX — это набор префиксных операторов, а также (, POSTFIX — это набор постфиксных операторов (если они есть), а также ), INFIX — это набор инфиксных операторов (сложение, вычитание, умножение и т. д.), а OPERAND — это идентификатор или константа.

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

   При желании мы могли бы удалить круглые скобки из наборов PREFIX и POSTFIX и сделать OPERAND рекурсивным производством. Результирующая грамматика тривиально LL(1) [Примечание 2]:

   operand    => IDENTIFIER | CONSTANT | '(' expression ')'
   term       => operand | PREFIX operand | operand POSTFIX
   expression => term | term INFIX expression
   

   Проблема, однако, в том, что эта грамматика не фиксирует приоритет оператора. Он даже не пытается распознать тот факт, что a+b*c и a*b+c являются суммами, так что оператором верхнего уровня является + в обоих случаях, а не тот оператор, который стоит первым в выражении. (Если бы вы разбирали APL, это не было бы проблемой. Но большинство языков соответствуют обычным ожиданиям в отношении приоритета операторов.)

   Этот момент важен, потому что грамматика LL не может обрабатывать леворекурсивные продукции, а вам нужна леворекурсивная продукция, чтобы правильно анализировать левоассоциативный оператор. (То есть, чтобы правильно анализировать a-b-c как ((a-b)-c), а не (a-(b-c)), у которого было бы другое значение.) Опять же, вы могли бы возразить, что это придирка, поскольку вы могли бы постобработать дерево разбора, чтобы исправить ассоциативность. Это, безусловно, верно, но в результате грамматика, которую вы используете для анализа, отличается от грамматики, которую вы используете для объяснения синтаксиса языка. Это может или не может беспокоить вас.

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

3. Давайте предположим, что мы отбросим приведенные выше возражения и просто спросим: «Для каких широко используемых языков программирования можно использовать синтаксический анализатор LL?»

   Тем не менее, чтобы избежать мошенничества, мы действительно должны требовать, чтобы синтаксический анализатор LL имел фиксированный просмотр вперед и не требовал обратного отслеживания. Если вы разрешаете произвольный поиск вперед и назад, то вы значительно расширяете область анализируемых языков, но я утверждаю, что вы больше не находитесь в области ЯЛ. Это устранит, например, подмножество C++ без шаблонов и препроцессоров, даже несмотря на то, что общие реализации компиляторов используют синтаксические анализаторы рекурсивного спуска, поскольку для разрешения "Самый неприятный анализ" неоднозначность. (В любом случае, вы не можете удалить шаблоны из C++, а синтаксический анализ с помощью шаблонов действительно сложен. [Примечание 3])

   И Java, и Python были спроектированы так, чтобы LL (1) «псевдоразборчиво». Я считаю, что Haskell тоже попадает в эту категорию. C не может быть правильно проанализирован без семантической информации (классическая двусмысленность: является ли (x)*(y) приведением или умножением? - это зависит от того, было ли x определено типом или объявлено как переменная), но я почти уверен, что его можно захватить с помощью Парсер рекурсивного спуска без возврата. Я не изучал C# подробно, но этот ответ Эрика Липперта предполагает, что в некоторых случаях требуется откат.

Примечания

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

2. Это не совсем LL, потому что я не левый фактор. Но это достаточно легко сделать; Я оставлю это в качестве упражнения.

3. См. раздел Является ли C++ контекстно-зависимым или контекстно-зависимым?. Также классическая работа Тодда Вельдхуизена Шаблоны C++ завершены по Тьюрингу

Если я рассматриваю компьютерные языки шире, чем языки программирования, я считаю, что есть несколько декларативных языков, которые вы могли бы рассмотреть, хотя это также может зависеть от того, что вы считаете современным.

Возможные кандидаты:

• XML
• LLVM ИК
• многие языки конфигурации, такие как файлы INI
• некоторые сетевые протоколы
• некоторые форматы данных, например файлы CSV

Большинство (все?) разновидностей языков, описывающих регулярные выражения, не являются регулярными выражениями, а являются LL(1).

Для реальных языков программирования все они, вероятно, слишком стары, чтобы считаться современными, и многие из них имеют общие расширения, которые, вероятно, нарушают LL(k).

• языки ассемблера
• БАЗОВЫЙ
• ЛИСП
• Языки вирта: Pascal, Modula, Oberon
• Пролог

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