Pull to refresh

Написание компилятора LALR(1)-парсеров. Базовая теория

Algorithms *Compilers *

Введение, или зачем нужны синтаксические анализаторы


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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

Читать дальше →
Total votes 65: ↑61 and ↓4 +57
Views 19K
Comments 26

Написание компилятора LALR(1)-парсеров. Описание LR-генераторов

Algorithms *Compilers *

Предисловие


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

В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.
Читать дальше →
Total votes 28: ↑27 and ↓1 +26
Views 13K
Comments 2

Особенности написания и возможные фичи LR-генераторов

JavaScript *Algorithms *Compilers *

Введение


Добрый день.
В заключительной части про написание собственного генератора LALR-парсеров я бы хотел описать возможные особенности и фичи. Кроме того я опишу чего мне не хватало в существующих решениях и ради чего я начал писать свой велосипед.

Дабы задать контекст, сообщу, что грамматика для анализа — это ECMAScript, так же известный как JavaScript. Конкретная спецификация — ECMA-262, редакция 5.1 от июня 2011 года.
Читать дальше →
Total votes 17: ↑17 and ↓0 +17
Views 5.9K
Comments 4