<<
>>

Конечные автоматы и альтернативы

Я упомянул, что регулярные выражения могут анализироваться с использованием конечного автомата. В большинстве книг по компиляторам а также в большинстве компиляторов, вы обнаружите, что это применяется буквально.

Обычно они имеют настоящую реализацию конечного автомата с целыми числами, используемыми для определения текущего состояния и таблицей действий, выполняемых для каждой комбинации текущего состояния и входного символа. Если вы пишите «front end» для компилятора, используя популярные Unix инструменты LEX и YACC, это то, что вы получите. Выход LEX – конечый автомат, реализованный на C плюс таблица действий, соответствующая входной грамматике данной LEX. Вывод YACC аналогичен... исскуственный таблично-управляемый синтаксический анализатор плюс таблица, соответствующая синтаксису языка.

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

Фактически в пятой главе я предупредил вас, что если вы считает себя нуждающимся в этих вещах, возможно вы делаете что-то неправильно и не используете возможности Паскаля. Существует в основном два способа определить состояние конечного автомата: явно, с номером или кодом состояния и неявно, просто на основании того факта, что я нахожусь в каком-то определенном месте кода (если сегодня вторник, то это должно быть Бельгия). Ранее мы полагались в основном на неявные методы, и я думаю вы согласитесь, что они работают здесь хорошо.

На практике может быть даже не обязательно иметь четко определенный лексический анализатор. Это не первый наш опыт работы с многосимвольными токенами. В третьей главе мы расширили наш синтаксический анализатор для их поддержки и нам даже не был нужен лексический анализатор. Причиной было то, что в узком контексте мы всегда могли сказать просто рассматривая единственный предсказывающий символ, имеем ли мы дело с цифрой, переменной или оператором. В действительности мы построили распределенный лексический анализатор, используя процедуры GetName и GetNum.

Имея ключевые слов мы не можем больше знать с чем мы имеем дело до тех пор, пока весь токен не будет прочитан. Это ведет нас к более локализованному сканеру, хотя, как вы увидите, идея распределенного сканера все же имеет свои достоинства.

<< | >>
Источник: Креншоу Джек. Давайте создадим компилятор!. 1999

Еще по теме Конечные автоматы и альтернативы:

  1. Игровые автоматы
  2. «автомат общественного мнения».
  3. 3. Продажа товаров с использованием автоматов
  4. Статья 703. Продажа товаров с использованием автоматов
  5. 14.2. Реализация моделей клеточных автоматов на ЭВМ
  6. РАЗДЕЛ П. АЛЬТЕРНАТИВЫ СОЦИОЛОГИИ
  7. Ложные альтернативы
  8. НАСЛАЖДЕНИЕ КОНЕЧНОЕ
  9. ФАНТОМ КОНЕЧНОСТИ
  10. Конечные причины
  11. Альтернативы истинные и ложные
  12. 2. Альтернативы имеют небольшой уровень общности
  13. СОСРЕДОТОЧЬТЕСЬ НА КОНЕЧНОМ РЕЗУЛЬТАТЕ
  14. Альтернативы истинные и ложные
  15. 1. Альтернативы имеют слишком большой уровень общности.
  16. ДУМАЙТЕ О КОНЕЧНОЙ ЦЕЛИ
  17. Правило ущербности альтернативы