Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм, выполняющий токенизацию и разбор в один шаг.
An algorithm that performs tokenization and parsing in a single step
В информатике, разбор без сканера (также называемый лексически-независимым разбором) выполняет токенизацию (разбиение потока символов на токены) и разбор (организация токенов во фразы) за один шаг, вместо разделения на конвейер из лексера и парсера, работающих последовательно. Грамматика языка считается лексически-независимой, если она использует единый формализм для описания как лексического (уровня токенов), так и синтаксического (уровня фраз) строения языка. Разделение обработки на лексер и парсер обеспечивает большую модульность; разбор без сканера обычно применяется, когда чёткое разделение между лексером и парсером не требуется или нежелательно. Примеры, когда это целесообразно, включают TeX, большинство грамматик вики-разметки, makefiles, простые специализированные языки сценариев и Raku.
In computer science, scannerless parsing (also called lexerless parsing) performs tokenization (breaking a stream of characters into words) and parsing (arranging the words into phrases) in a single step, rather than breaking it up into a pipeline of a lexer followed by a parser, executing concurrently. A language grammar is scannerless if it uses a single formalism to express both the lexical (word level) and phrase level structure of the language. Dividing processing into a lexer followed by a parser is more modular; scannerless parsing is primarily used when a clear lexer–parser distinction is unneeded or unwanted. Examples of when this is appropriate include TeX, most wiki grammars, makefiles, simple application specific scripting languages, and Raku.
Недостатки
Поскольку лексическое сканирование и синтаксический анализ объединены, результирующий анализатор, как правило, оказывается более сложным и, следовательно, труднее для понимания и отладки. То же самое справедливо и для соответствующей грамматики, если она используется для генерации анализатора. Результирующий анализатор, как правило, значительно менее эффективен по времени и потреблению памяти, чем конвейер "лексер-анализатор".
Since the lexical scanning and syntactic parsing are combined, the resulting parser tends to be more complicated and thus harder to understand and debug. The same will hold for the associated grammar, if a grammar is used to generate the parser. The resulting parser tends to be significantly less efficient than a lexer parser pipeline with regard to both time and memory.
Реализация
SGLR — это парсер для модульного формализма определения синтаксиса (SDF), являющийся частью метасреды ASF+SDF и системы преобразования программ Stratego/XT. JSGLR — это чистая Java-реализация SGLR, также основанная на SDF. TXL поддерживает разбор на уровне символов. dparser генерирует код ANSI C для GLR-парсеров без сканера. Spirit позволяет выполнять как бессканерный, так и сканерный разбор. SBP — бессканерный парсер для булевых грамматик (супермножество контекстно-свободных грамматик), написанный на Java. Laja — двухфазный генератор бессканерного парсера с поддержкой отображения правил грамматики в объекты, написанный на Java. Система грамматик Raku является особенностью языка программирования общего назначения Raku. PyParsing — бессканерный парсер, написанный на чистом Python. META II имеет встроенные функции парсинга токенов. TREE META, как и META II, также является бессканерным и имеет встроенные функции лексера. CWIC — компилятор для разработки и реализации компиляторов, включающий правила для токенов в свой язык. Правила в CWIC компилировались в булевы функции, возвращающие значение "успех" или "неудача".
SGLR is a parser for the modular Syntax Definition Formalism (SDF), and is part of the ASF+SDF Meta Environment and the Stratego/XT program transformation system. JSGLR, a pure Java implementation of SGLR, also based on SDF. TXL supports character level parsing. dparser generates ANSI C code for scannerless GLR parsers. Spirit allows for both scannerless and scanner based parsing. SBP is a scannerless parser for boolean grammars (a superset of context free grammars), written in Java. Laja is a two phase scannerless parser generator with support for mapping the grammar rules into objects, written in Java. The Raku grammars feature of the general purpose programming language Raku. PyParsing is a scannerless parser written in pure Python. META II Has built in token parsers functions. TREE META Like META II also is scannerless having builtin lexer functions. CWIC compiler for writing and implementing compilers. Has token rules as part of its language. Rules in CWIC were compiled into boolean functions returning success or failure.