Comments 38
Семантический анализ, автоматический вывод типов и прочее зависят от исходного языка, а следовательно, это тоже части фронтенда. Миддл-энд работает с промежуточным представлением, которое в общем случае не зависит ни от исходного, ни от целевого языка.
Диаграмма структуры компилятора просто чудесна и абсолютно универсальна.
передняя часть — серединка — задняя часть
передняя часть — серединка — задняя часть
Из статьи неясно зачем нужно выделять токенизацию или лексический анализ отдельно от основного парсера. Почему бы не интегрировать токенизацию прямо в рекурсивный спуск парсера — получим один проход вместо двух и заодно возможность контекстно-зависимых ключевых слов
UFO just landed and posted this here
заодно возможность контекстно-зависимых ключевых слов
Как связана интегрируемость токенизатора с возможностью использования контекстно-зависимых ключевых слов? Их и так можно использовать в контекстно свободном парсере на токенах.
Ну, допустим, пример из синтаксиса Lua (подсветка хабра не справляется).
Количество символов '=' в начале и конце блока комментария должно совпадать. Как это реализовать не совмещая токенизацию и парсинг? А что делать, если в требуемом синтаксисе части с подобной зависимостью не находятся в пределах одного токена, а разделены кучей других?
--[[comment]]
--[=[com]]ment]=]
--[==[com]]=]ment]==]
--[===[com]]=]==]ment]===]
Количество символов '=' в начале и конце блока комментария должно совпадать. Как это реализовать не совмещая токенизацию и парсинг? А что делать, если в требуемом синтаксисе части с подобной зависимостью не находятся в пределах одного токена, а разделены кучей других?
Очень просто. Не использовать таких сложно устроенных комментариев в своем языке.
Можно. В ANTLR для такого существуют семантические предикаты и действия, в которых можно писать код на целевом языке, который может делать что угодно, например, считать точное соответствие символов =.
Каждое '=' — один токен, а уж парсер ищет один, два или сколько надо этих токенов подряд.
Кстати, это можно реализовать обычными регулярками
/\-\-\[(?P<comment>=+).*?(P=comment)\], а это всё же не полноценный LL\LR парсер, а ограниченная кс-граммтика.
- Алгоритмическую сложность это не меняет :)
- Единственная ответственность
- На PHP я реализовал токенайзер на генераторах и два прохода по сути идут параллельно :)
На PHP я реализовал токенайзер на генераторах и два прохода по сути идут параллельно :)
Тут есть несколько проблем:
- Нормальный (по скорости) лексер на пыхе возможен только с использованием preg_match_all/preg_replace_callback, т.е. с полным анализом всего и сразу.
- Даже если написать вручную это дело или используя preg_match, то нужен буфер для всяких lookahead в парсере.
А ещё я бы попросил ссылочкой на гитхаб в меня покидаться, не отказался бы посмотреть на это дело, можно?)
Я тоже реализовывал на ANTLR: php grammar. Поддерживаются интерполируемые строки, альтернативный синтаксис, Heredoc строки.
Кажется, я не очень удачно выразился. Это интерпретатор простенького языка, написанный на PHP в качестве тестового задания, а не интерпретатор PHP на PHP. Пока на гитхаб не выкладывал, чтоб конкуренты на вакансию не увели :)
При использовании генераторов парсеров это приведет к раздуванию таблиц, сильному увеличению времени рабты генератора и увеличению выходного файла.
Но совмещение лексера и парсера часто применяют при использовании парсерных комбинаторов. По моему опыту сильный недостаток этого подхода — в гармматике приходится тщательно прописывать, где разрешены комментарии.
Но совмещение лексера и парсера часто применяют при использовании парсерных комбинаторов. По моему опыту сильный недостаток этого подхода — в гармматике приходится тщательно прописывать, где разрешены комментарии.
Подход официально называется scannerless parsing. При использовании передовых генераторов синтаксического разбора (см., например, SDF3 и статью) такой подход показывает себя наилучшим образом.
Не совсем понимаю, в чем состояли Ваши затруднения при работе с комбинаторами. Вот пример их использования для игрушечного Си-подобного языка. Как можно видеть, комментарии поддерживаются без каких-либо специальных усилий:
github.com/true-grue/PigletC/blob/master/src/parse.py
Не совсем понимаю, в чем состояли Ваши затруднения при работе с комбинаторами. Вот пример их использования для игрушечного Си-подобного языка. Как можно видеть, комментарии поддерживаются без каких-либо специальных усилий:
github.com/true-grue/PigletC/blob/master/src/parse.py
Комментарии могут располагаться между любыми токенами. Если их не рыбрасывать в лексере, то в парсере этим приходится заниматься во многих местах и что-нибудь очень легко пропустить.
Примерно так:
Примерно так:
val functionCallArgs: P[Seq[EXPR]] = comment ~ baseExpr.rep(sep = comment ~ "," ~ comment) ~ commentЯ вижу, что Вы проигнорировали приведенный выше код и это меня, признаюсь, несколько огорчило. Но попробую объяснить на словах.
Комбинаторы — удобный способ создавать простые eDSL на языке, который поддерживает механизм лексических замыканий. Соответственно, комбинаторами мы можем описать БНФ-грамматику, разбор для которой может быть на деле совершенно произвольным.
По-настоящему популярным подход без выделенной стадии лексического анализа стал с появлением работ по PEG (напомню, что одна из сильных сторон scannerless-подхода — удобное описание вложенных грамматик). Соответственно, далее я буду рассматривать PEG-комбинаторы. Если мы посмотрим на классическую уже статью Форда, то увидим в одном из примеров набор правил, часть которых относится к уровню лексического разбора, а другая — к синтаксическому разбору.
Здесь сразу становится понятно, что как отдельную сущность, в духе Вашего примера на Scala, комментарии выносить на уровень синтаксических правил совершенно излишне. Но остается Spacing, который действительно повторяется достаточно часто.
В таких системах, как Ometa и Ohm, Spacing неявно вызывается при указании правила для соотв. токена. Например, в Ometa Spacing будет вызван, если Вы в качестве имени правила указали класс токена в кавычках. Комбинаторы же сильны своей программируемостью и мы всегда можем задать удобную для нас функцию высшего порядка, в духе:
Здесь, kw и op занимаются, в том числе, разбором пробельных элементов. Ну а Ваш пример будет выглядеть следующим образом:
В целом, я бы порекомендовал перед использованием готовых комбинаторов поупражняться в создании игрушечной системы на основе PEG. Поскольку, как я уже сказал выше, комбинаторы хороши своей программируемостью и Вы мало выиграете, если будете только пассивно пользоваться готовыми возможностями.
Комбинаторы — удобный способ создавать простые eDSL на языке, который поддерживает механизм лексических замыканий. Соответственно, комбинаторами мы можем описать БНФ-грамматику, разбор для которой может быть на деле совершенно произвольным.
По-настоящему популярным подход без выделенной стадии лексического анализа стал с появлением работ по PEG (напомню, что одна из сильных сторон scannerless-подхода — удобное описание вложенных грамматик). Соответственно, далее я буду рассматривать PEG-комбинаторы. Если мы посмотрим на классическую уже статью Форда, то увидим в одном из примеров набор правил, часть которых относится к уровню лексического разбора, а другая — к синтаксическому разбору.
...
DOT <- ’.’ Spacing
Spacing <- (Space / Comment)*
Comment <- ’#’ (!EndOfLine .)* EndOfLine
...
Здесь сразу становится понятно, что как отдельную сущность, в духе Вашего примера на Scala, комментарии выносить на уровень синтаксических правил совершенно излишне. Но остается Spacing, который действительно повторяется достаточно часто.
В таких системах, как Ometa и Ohm, Spacing неявно вызывается при указании правила для соотв. токена. Например, в Ometa Spacing будет вызван, если Вы в качестве имени правила указали класс токена в кавычках. Комбинаторы же сильны своей программируемостью и мы всегда можем задать удобную для нас функцию высшего порядка, в духе:
seq(kw("if"), op("("), expr, op(")") ...Здесь, kw и op занимаются, в том числе, разбором пробельных элементов. Ну а Ваш пример будет выглядеть следующим образом:
args = list_of(expr, op(","))В целом, я бы порекомендовал перед использованием готовых комбинаторов поупражняться в создании игрушечной системы на основе PEG. Поскольку, как я уже сказал выше, комбинаторы хороши своей программируемостью и Вы мало выиграете, если будете только пассивно пользоваться готовыми возможностями.
При использовании генераторов парсеров это приведет к раздуванию таблиц, сильному увеличению времени рабты генератора и увеличению выходного файла.
Тут можно поспорить, насколько сильное это увеличение времени. Зато генераторы парсеров дают: быстрая разработка, возможность генерации под разные языки, обработка ошибок из коробки, как и обработка скрытых токенов (как комментарии).
Я имел в виду не генераторы парсеров, а потоковый лексер/токенайзер, использующий генераторы как сахар для потока. Думаю над потоковым парсером, но ещё не понял возможно ли AST в принципе выдавать как поток для Си-подобных языков и имеет ли это какой-то смысл.
Обычно — это просто разделение ответственностей, не обязательно лексический анализатор должен полностью пройтись по исходнику и сохранить все токены чтобы потом еще раз по токенам идти, можно делать это параллельно, скажем вызвал синтаксический анализатор метод
lexer->getNextToken() лексер прочитал следующий токен и остановился, попутно сохранив offset. В итоге это просто инкапсуляция чтобы не думать о токенизации во время написания синтаксического анализатора.
Мне кажется, что в основном в классической литературе на русском языке про компиляторы (в том числе и переводимой) принято называть этап не «парсинг», а синтаксический анализ.
Просто как небольшое примечание.
Просто как небольшое примечание.
Достойное примечание, напомнило про «октет» в французском вместо чуждого «байт». Исторически, боюсь, «лексический анализ» уступит «парсингу», увы. Кстати, с языковой точки зрения «лексический анализ» — устаревшее заимствование, архаичное, в сравнении с более современным заимствованием «парсинг».
Мне кажется, Вы путаете, построение AST, про которое в данной статье написано в разделе «Парсинг», относится к синтаксическому анализу, так в создании компиляторов называется данный этап, в том числе и на английском (в том же Dragon Book). «Парсинг» же это несколько другое понятие в разработке. Это не замечание про чистоту языка, а замечание про принятую терминологию в данной сфере.
Не хотел спорить — однако, заглянул в это обсуждение месяц спустя по другому поводу, заодно попробовал прояснить для себя этот терминологический вопрос (и пока решил остаться при своём мнении). Попадётся на глаза Dragon Book, загляну. Однако, на данный момент я в своей неправоте не убеждён — например, англоязычная Википедия перенаправляет «Syntax Analysis» на «Parsing» — страницу, начинающуюся с фразы «Parsing, syntax analysis, or syntactic analysis is the process of analysing a string of symbols, …». Далее, русская программистская терминология довольно последовательно следует за английской по понятным причинам.
Википедия, конечно, не истина в последней инстанции, но в моих глазах она довольно авторитетна, по крайней мере по околопрограммистским и околоматематическим темам.
По поводу предметности несогласия о терминологии: язык меняется со временем (я написал предыдущей комментарий на основании субъективных наблюдений — со временем «парсинг» попадается чаще и чаще в местах, где раньше я бы ожидал прочитать «синтаксический анализ»). «Абсолютная истина» может быть определена в узких (по тематике и времени) контекстах; более предметным спор становится в кругу экспертов (мне же с парсингом / синтаксическим анализом не так часто приходится иметь дело — большей ясности хотелось для себя лично).
В условиях неоднозначности я, если мне это сильно занятно, пытаюсь выяснить наиболее частое словоупотребление, и использовать именно его. Пример — ошибочно использовал везде слово «компонента» в женского роде (как в «компонента связности» и в прочих математических и физических «компонентах»), удивляясь, всё чаще встречая его в мужском роде (учился я на математическом факультете, а работать стал программистом). Постепенно осознал, что при употреблении в инженерном контексте большинство собеседников употребляют слово «компонент» в мужском роде, так что ввиду этого мне следует себя переучить — и вообще, это два разных слова, которые я принимал за одно (да, так и есть, ещё раз заглянул в Википедию, русскоязычную уже на этот раз). Возможное различие в словоупотреблении «парсинг» и «синтаксический анализ» беру на заметку, но пока — не убеждён.
Википедия, конечно, не истина в последней инстанции, но в моих глазах она довольно авторитетна, по крайней мере по околопрограммистским и околоматематическим темам.
По поводу предметности несогласия о терминологии: язык меняется со временем (я написал предыдущей комментарий на основании субъективных наблюдений — со временем «парсинг» попадается чаще и чаще в местах, где раньше я бы ожидал прочитать «синтаксический анализ»). «Абсолютная истина» может быть определена в узких (по тематике и времени) контекстах; более предметным спор становится в кругу экспертов (мне же с парсингом / синтаксическим анализом не так часто приходится иметь дело — большей ясности хотелось для себя лично).
В условиях неоднозначности я, если мне это сильно занятно, пытаюсь выяснить наиболее частое словоупотребление, и использовать именно его. Пример — ошибочно использовал везде слово «компонента» в женского роде (как в «компонента связности» и в прочих математических и физических «компонентах»), удивляясь, всё чаще встречая его в мужском роде (учился я на математическом факультете, а работать стал программистом). Постепенно осознал, что при употреблении в инженерном контексте большинство собеседников употребляют слово «компонент» в мужском роде, так что ввиду этого мне следует себя переучить — и вообще, это два разных слова, которые я принимал за одно (да, так и есть, ещё раз заглянул в Википедию, русскоязычную уже на этот раз). Возможное различие в словоупотреблении «парсинг» и «синтаксический анализ» беру на заметку, но пока — не убеждён.
Октет и байт — разные понятия, используемые в разных контекстах. Байт — единица адресации памяти, октет — просто 8 двоичных (обычно) разрядов.
Вы пишите о англоязычной (перешедшей также в русский язык) терминологии, а я упомянул французскую, вспомнив рассказ учителя программирования 30-летней давности примерно. Насколько справедливо это утверждение (о том, что французы используют французское слово «октет» в значении английского / русского «байт»?) было тогда, и насколько справедливо оно сейчас? Точно не знаю, но беглая проверка поисковиками меня убедила, что скорее, оно было и остаётся справедливым. Спрошу при случае у коллеги-француза.
Немного обидно читать про «владение» там, где хотелось услышать про линейную логику. Упор на иммутабельные (пардон, неизменяемые) локальные переменные при том, что поля структур мутабельные (пардон, изменяемые) по умолчанию… Ой, встаньте дети, встаньте в Krug.
foo* bar;
bar.b = 3;
Хех, найди ошибку, что называется)
Sign up to leave a comment.
Краткий и бодрый обзор архитектуры компиляторов