Где я могу изучить основы написания лексера?

86

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

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

На данном этапе меня не особо интересуют передовые практики или методы оптимизации, я предпочитаю сосредоточиться на главном. Какие полезные ресурсы помогут мне начать работу?

Руперт Мэдден-Эбботт
источник

Ответы:

73

В основном есть два основных подхода к написанию лексера:

  1. Создание рукописного учебника, и в этом случае я рекомендую этот небольшой урок .
  2. Используя некоторые инструменты генератора лексеров, такие как lex . В этом случае я рекомендую прочитать руководства по выбору конкретного инструмента.

Также я хотел бы порекомендовать учебник Kaleidoscope из документации LLVM . Он проходит через реализацию простого языка и, в частности, демонстрирует, как написать небольшой лексер. Существует версия учебника на C ++ и Objective Caml.

Классический учебник по этому предмету - Составители: принципы, методы и инструменты, также известный как «Книга дракона». Однако это, вероятно, подпадает под категорию «довольно продвинутых описаний».

витаут
источник
4
Учебник по калейдоскопу был той частью, которая действительно ответила для меня на этот вопрос.
Роберт Байерс,
Для получения дополнительной информации о написании парсера LL (1) вручную см. Этот ответ .
jchook
12

Книга Дракона, вероятно, является исчерпывающим руководством по этому вопросу, хотя может быть немного подавляющим. Шаблоны реализации языка и прагматика языка программирования также являются отличными ресурсами.

Брэндон Моретц
источник
5
+1 к книге Дракона. Многому научился, когда учился в университете. Да, там много всего, но если вы действительно заинтересованы в разработке и реализации компилятора, это отличный ресурс.
DarinH 02