Токенизация номеров для парсера

Question

Я пишу свой первый парсер и у меня есть несколько вопросов, касающихся токенизатора.

По сути, мой токенизатор предоставляет функцию nextToken(), которая должна возвращать следующий токен. Эти токены различаются по типу токенов. Я думаю, что имеет смысл иметь следующие типы токенов:

• СИМВОЛ (например, <, :=, ( и т. П.
• БЕЛЫЙ ПРОБЕЛ (табуляция, новые строки, пробелы ...)
• ЗАМЕЧАНИЕ (комментарий между / * ... * / или после // через новую строку)
• НОМЕР
• IDENT (например, имя функции или переменной)
• STRING (что-то заключенное между "....")

Теперь, как вы думаете, это имеет смысл?

Кроме того, я борюсь с токеном NUMBER. Как вы думаете, имеет ли смысл разделить его на токены типа NUMBER и FLOAT? Без FLOAT типа токена я получил бы NUMBER (например, 402), SYMBOL (.), А затем еще NUMBER (например, 203), если я собирался проанализировать float.

Наконец, что, по вашему мнению, имеет больше смысла для возврата токенизатора, когда он встречает -909? Должен ли он сначала вернуть SYMBOL -, а затем NUMBER 909 или сразу же вернуть NUMBER -909?

Answer 1

Это зависит от вашего целевого языка.

Смысл лексера - возвращать токены, которые облегчают написание парсера для вашего языка. Предположим, ваш лексер возвращает NUMBER, когда видит символ, который соответствует «[0-9] +». Если он увидит нецелое число, такое как «3.1415926», он вернет NUMBER . NUMBER. Хотя вы можете справиться с этим в вашем парсере, если ваш лексер выполняет соответствующую работу по пропуску пробелов и комментариев (так как они не имеют отношения к вашему парсеру), вы можете в итоге неправильно анализировать такие вещи, как "123 / * comment /. \ n / другой комментарий * / 456 "как числа с плавающей запятой.

Что касается выражения "- [0-9] +" как NUMBER против MINUS NUMBER, опять же, это зависит от вашего целевого языка, но я бы обычно использовал MINUS NUMBER, иначе Вы бы в конечном итоге лексировали "A = 1-2-3-4" как SYMBOL = NUMBER NUMBER NUMBER NUMBER вместо SYMBOL = NUMBER MINUS NUMBER MINUS NUMBER MINUS NUMBER.

Пока мы обсуждаем эту тему, я настоятельно рекомендую книгу Терренса Парра, автора ANTLR .

Шаблоны языковой реализации .

Answer 2

Лучше всего, если ваши типы токенов будут точно соответствовать терминальным символам вашей грамматики.

Не зная языка / грамматики, я ожидаю, что вам будет лучше обслужить наличие типов токенов для "LESS_THAN", "LESS_THAN_OR_EQUAL", а также "FLOAT", "DOUBLE", "INTEGER" и т. Д.

Answer 3

Из моего опыта с реальными лексерами:

1. Убедитесь, что вам действительно нужны маркеры комментариев / пробелов. Как правило, компиляторы не нуждаются в них, в то время как интегрированные среды разработки часто нуждаются (например, для окрашивания комментариев в зеленый цвет).
2. Обычно нет ни одного токена «оператора»; вместо этого есть токен для каждого отдельного оператора. Таким образом, есть токен PLUS, токен AMPERSAND, токен LESSER_THAN и т. Д. Это означает, что вы заботитесь о лексеме (фактическом сопоставленном тексте), когда токен является идентификатором или неким литералом.
3. Избегайте расщепления литералов. Если "hello world" является строковым литералом, проанализируйте его как один токен. Если -3.058e18 является литералом с плавающей запятой, также проанализируйте его как один токен. Лексеры обычно полагаются на регулярные выражения, которые достаточно выразительны для всех этих вещей, и даже больше. Конечно, если литералы достаточно сложны, у вас есть для их разделения (например, литерал блока в Smalltalk).

Answer 4

Я думаю, что ответ на ваш вопрос строго связан с семантикой NUMBER. Какой НОМЕР должен быть? Всегда положительное целое число, число с плавающей точкой ...

Я хотел бы предложить вам ознакомиться с инструментами flex и yacc (aka lex & bison) операционных систем U ** x: это мощные генераторы синтаксических анализаторов и сканеров, которые принимают грамматику и выводят компилируемый и легко полезная программа.

Answer 5

Это зависит от того, как вы берете токены, если вы делаете это символ за символом, то это может быть немного сложно, но если вы делаете это слово за словом, то есть

int a = a + 2.0

, тогдатокены будут (без пробелов)

int
a
=
a
+
2.0

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