Компиляция. 2: грамматики

[shai_xylyd]

Синтаксис языка это дело десятое, не самое интересное в строении компилятора,
кроме того часто выбор синтаксиса ограничивает остальные, куда более интересные
внутренности, такие как энергичность языка, система типов, объектная модель,
модель работы с памятью, макросистему…

Мне, да и не только мне кажеться, что логично начать как раз с этих особенностей:
реализовать объектную модеть программы (DOM, AST), поиграть с ней, внести изменения,
написать юнит тесты, а только потом, когда все устаканиться, замапить синтаксис на
эту структуру.

Если касаться парсеров, то стоит не только писать о классике (LR(1), lex), но и об
относительно новых достижениях — PEG и Packrat, позволяющий «смешивать» языки.

[shai_xylyd]

Забыл добавить ссылку на такое же, только более развернутое мнение (описание создания своего языка) — thedeemon.livejournal.com/9974.html

[braindamaged]

К вашей ссылке можно добавить еще одну (разработчик языка Beep, описанного в fprog.ru): dmzlj.livejournal.com/129758.html

[tyomitch]

Естественно, что вкусы у всех разные: одним не хватает в этом тексте теории автоматов и иерархии Хомского, другим скучно от парсинга и хочется в первую очередь семантику.

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

За ссылку спасибо.

[kosiakk]

Есть языки программирования без синтаксиса вообще, следовательно и без парсинга оного.

Jetbrains MPS, LabView, App Inventor for Android или любой другой визуальный язык.

Так что в первую очередь стоит думать о высоких задачах и целях. Остальное — технические мелочи

[kosiakk]

опять же, выступлю со своим любимым языком программирования Scala и скажу, что там написание подобных парсеров встроено прямо в стандартную библиотеку: Parser Combinators.

код будет такой:

object NumberParsers extends util.parsing.combinator.RegexParsers {
var EXPR:Parser[Any] = NUM | (EXPR ~ OP ~ EXPR)
var NUM = DIGIT +
var DIGIT= «0-9»r
var OP = "[+*/-]«r
}

Это весь код, он компилируется. Указание типа у EXPR требуется из-за рекурсии.
Сравним с научной текстовой формой записи:

EXPR: NUM | EXPR OP EXPR;
NUM: DIGIT | NUM DIGIT;
DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
OP: '+' | '-' | '*' | '/';

Мне кажется, Скала даже немного выигрывает в читабельности, особенно при определении NUM. Синтаксис „DIGIT +“ означает что NUM это более одного объекта DIGIT

[tyomitch]

Не понимаю. Что получается в итоге? Рекурсия с бэктрекингом, как «ленивый слон» по ссылке выше?
Что на выходе у парсера? Дерево?

[kosiakk]

на выходе дерево с явным указанием типов.

мы делаем так:

var AST = parseAll( EXPR, inputText)

и переменная AST заполняется разобранным деревом одного выражения из inputText
более того, каждый узел можно преобразовывать. Например, мы хотим чтобы NUM был типа Int а не String:

var NUM = (DIGIT + ) ^^ {s => s.toInt }

тогда компилятор Скалы поймёт что NUM имеет тип Parser[Int] и учтёт это в AST.
вообще надо бы топик написать.

[kosiakk]

не совсем так, конечно.

на вход анонимной функции { s =>… } приходит не строка, а List[String], т.к. каждый DIGIT вычисляется в строку, а NUM это список из нескольких таких строк, как мы и просили.

Так что придётся строки сначала объединить, а потом уже преобразовать в число: { list => list.mkString.toInt }
Ну или возложить эту работу изначально на regexp, тогда от DIGIT можно отказаться вообще:

var NUM = "[0-9]+«r ^^ { s => s.toInt }

[kosiakk]

т.е. EXRP это функция, которая умеет парсить выражения.
замечу что это всё компилируется непосредственно в байт-код, без промежуточных утилит вроде YACC
и является правильным кодом на языке скала, без какой-либо особой поддержки со стороны синтаксиса или компилятора языка.

[kosiakk]

простите, внутри рекурсия с бэк-трекингом, конечно же.

[mraleph]

какой смысл описывать весь этот «матан» снова и снова?

калькуляторы lex+yacc вообще на каждом углу валяются, бери сколько унесешь. только вопрос как это поможет человеку программирующему на чем-нибудь типа Java/C#/Python/Ruby/Javascript остается открытым.

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

[tyomitch]

Главное ведь что, на мой взгляд? Дать прочуствовать архитектуру, инженерные решения

Именно поэтому акцент на «как оно работает», а не на «как закодить грамматику на yacc».
А без «матана» программирование превращается в шаманство: «у меня есть парсер, работает — и ладно, не моё дело как».

[mraleph]

разумно. но на мой взгляд как оно работает «матан» сам по себе не позволяет прочуствовать: надо писать руками либо разборщик для конкретного языка, либо генератор LR-разборщиков.

[tyomitch]

Ничего не понял, что с чем не смешивать.
У регэкспов есть конкретное математическое определение, доказуемо равномощное регулярным грамматикам.

[tyomitch]

По вашей же ссылке и написано: «Perl's pattern-matching constructs have exceeded the capabilities of formal regular expressions»

Переведу: «Возможности распознавания текста в Perl вышли за рамки регулярных выражений». (Но некоторые пользователи по привычке продолжают их называть регэкспами.)

Даже если «в военное время пи может достигать четырёх», это не означает, что «в наше время» регулярные выражения (математический объект!) «научились» чему-то, чего раньше не могли.

[aabzel]

Как понять синтаксис и семантики того языка на котором вы определяете грамматику?