каково различие между законом и yacc

Да, YACC - это парсер, Lex - лексический анализатор. Обычно они используются вместе: вы Lex вводите строку, а YACC - токенизированный ввод, предоставляемый Lex.

Теперь регулярное выражение может представлять только регулярные языки. Одно из ограничений обычного языка - нехватка «памяти». Вы не можете определить правила принятия дальше по строке, основываясь на том, что было раньше.

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

Можно также изменить вопрос. Если YACC может больше, почему бы не использовать его для лексического анализа? Что ж, так уж получилось, что вы можете очень эффективно проверять правильность регулярного выражения, что не относится к общим грамматикам - не на том же уровне. Тем не менее, YACC может выполнять базовый лексический анализ, если лексические правила языка достаточно просты.

lex предназначен для токенизации ввода. То есть разделение вашего ввода на объекты нижнего уровня, которые определяет ваша грамматика. Например, вы используете lex для определения ключевых слов, идентификаторов, строк, комментариев, пробелов и т. Д.

yacc предназначен для синтаксического анализа вашей грамматики . Грамматика - это описание вашего языка, обычно определяемое в EBNF или какой-либо другой контекстно-свободной грамматике. После того, как вы опишете свою грамматику в yacc, вы можете использовать ее для выполнения действий вашего инструмента при распознавании элементов языка. Это может быть, например, построение синтаксических деревьев для решения выражений, определение объектов области видимости, запись определений переменных и т. Д.

Это дополнительные продукты.

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

Входной поток (символы) -> Lex (токены) -> Yacc (абстрактное синтаксическое дерево) -> ваше приложение

В общем, то, что Lex будет делать, - это читать исходный файл, с самого начала и попытайтесь сопоставить ряд регулярных выражений (у lex есть свой собственный, специальный синтаксис для этого, который немного отличается от регулярных выражений perl или sed), а затем будет вызывать другую программу с каждым токеном, который она признает. Токены могут быть либо просто перечислимым значением, например, для ключевого слова или оператора, либо к ним могут быть прикреплены некоторые метаданные, например, для буквального значения.

Lex обычно (хотя и не обязательно) используется для вызова Yacc. Yacc использует алгоритм парсера LALR, который, грубо говоря, работает, помещая каждый токен в стек. Если в стеке есть последовательность токенов, которую он распознает, он вытолкнет все токены, выполнит действие и вернет другой токен обратно в стек.

Правильный словарь того, над чем работает Yacc, - это терминалы и нетерминалы. Терминал - это токен, который он получил от вызывающей программы (обычно Lex), а нетерминал - это результат сопоставления последовательности в его стеке.

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

Yacc, как и lex, можно использовать отдельно от других. Например, вы можете использовать Yacc, передав ему отдельные символы из исходного текста, и используйте правила Yacc для распознавания каждого вида токенов. Однако Yacc не спроектирован таким образом, чтобы его можно было легко использовать, поэтому полученный лексер будет намного сложнее, чем эквивалентный лексер в Lex. Более типичным использованием будет создание лексера с ручным кодированием по причинам производительности или потому, что вам нужен более умный лексер. Типичный пример второго случая - использование в C-подобных языках, которые должны знать о предыдущем использовании идентификаторов, чтобы знать, используются ли они для описания типов или переменных.

lex - это лексический анализатор . Он разбивает текст на токены. Его мощность примерно эквивалентна сопоставлению регулярных выражений. yacc - это генератор парсеров . Он берет последовательность токенов (скажем, из lex) и интерпретирует их как серию операторов. Его возможности примерно эквивалентны контекстно-свободным грамматикам.

Типичное применение lex и yacc - для реализации языков программирования. lex токенизирует ввод, разбивая его на ключевые слова, константы, знаки препинания и т. д. Затем yacc реализует реальный компьютерный язык; распознавание, например, оператора for или определения функции.

В практическом смысле вы часто используете lex для обработки вводимого текста на фрагменты. Затем вы используете yacc, чтобы связать эти фрагменты вместе и преобразовать их в более широкий смысл.

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

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