В чем разница между lex и yacc

Ответ 1

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

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

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

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

Ответ 2

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

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

Это бесплатные продукты.

Ответ 3

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

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

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

Ответ 4

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

Входной поток (символы) → Лекс (токены) → Yacc (Абстрактное дерево синтаксиса) → Ваша аппликация

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

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

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

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

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

Ответ 5

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

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