Войти
В компьютерном программировании, то лексер обходной является общим решением проблем в разборе ANSI C, из - за эталонную грамматику будучи контекстно-зависимым. В языке C для классификации последовательности символов как имени переменной или имени типа требуется контекстная информация о структуре фразы, что не позволяет иметь контекстно-свободный лексер.
Проблема в том, что в следующем коде лексический класс Aне может быть определен без дополнительной контекстной информации:
(A)*B
Этот код может быть умножением двух переменных, в этом случае Aэто переменная; написано однозначно:
A * B
В качестве альтернативы это может быть приведение разыменованного значения Bк типу A, в этом случае Aэто имя typedef; написано однозначно:
(A) (*B)
Более подробно, в компиляторе лексический анализатор выполняет один из самых ранних этапов преобразования исходного кода в программу. Он сканирует текст для извлечения значимых маркеров, таких как слова, числа и строки. Парсер анализирует последовательности токенов, пытаясь сопоставить их с правилами синтаксиса, представляющими языковые структуры, такие как циклы и объявления переменных. Здесь возникает проблема, если одна последовательность токенов может неоднозначно соответствовать нескольким синтаксическим правилам.
Эта неоднозначность может произойти в C, если лексер не различает идентификаторы переменной и typedef. Например, в выражении C:
(A) * B
лексер может найти эти токены:
Проблема заключается в том, что именно лексический класс A не может быть определена без дополнительного контекста: анализатор может интерпретировать это как переменную A, умноженную на B или как тип А отливки разыменованного значения B. Это известно как проблема "typedef-name: identifier" из-за имени проблемного производственного правила.
Решение обычно состоит в передаче информации из таблицы семантических символов обратно в лексер. То есть вместо того, чтобы функционировать как чистый односторонний конвейер от лексера к синтаксическому анализатору, существует обратный канал от семантического анализа обратно к лексеру. Такое смешение синтаксического анализа и семантического анализа обычно считается неэлегантным, поэтому его называют «взломом».
Без добавленного контекста лексический анализатор не может отличить идентификаторы типа от других идентификаторов, потому что все идентификаторы имеют одинаковый формат. С помощью взлома в приведенном выше примере, когда лексер находит идентификатор A, он должен иметь возможность классифицировать токен как идентификатор типа. Правила языка можно пояснить, указав, что для приведения типов требуется идентификатор типа, и двусмысленность исчезнет.
Проблема также существует в C ++, и парсеры могут использовать тот же прием.
Эта проблема не возникает (и, следовательно, не требует "взлома" для решения) при использовании методов лексерного синтаксического анализа, поскольку они по сути являются контекстными. Однако они, как правило, считаются менее элегантными, поскольку им не хватает модульности, связанной с одновременным наличием в конвейере лексического анализатора и парсера.
Некоторые генераторы синтаксического анализатора, такие как производный от byacc BtYacc ("Backtracking Yacc"), дают сгенерированному синтаксическому анализатору возможность попробовать несколько попыток синтаксического анализа токенов. В описанной здесь проблеме, если попытка не удалась из-за семантической информации об идентификаторе, она может вернуться назад и попытаться выполнить другие правила.
Clang анализатор обрабатывает ситуацию совершенно иначе, а именно с использованием не эталонный лексическим грамматики. Лексер Clang не пытается различать имена типов и имена переменных: он просто сообщает текущий токен как идентификатор. Затем синтаксический анализатор использует библиотеку семантического анализа Clang, чтобы определить природу идентификатора. Это позволяет гораздо более четко разделить задачи и инкапсулировать лексер и синтаксический анализатор, и поэтому некоторые разработчики компиляторов считают, что это гораздо более элегантное решение, чем Lexer Hack. Этот же подход используется в большинстве других современных языков, которые не различают разные классы идентификаторов в лексической грамматике, а вместо этого откладывают их на этап синтаксического анализа или семантического анализа, когда имеется достаточная информация.
