Regex, написание игрушечного компилятора, разбор, удаление комментариев

Question

В настоящее время я работаю над этой книгой: http://www1.idc.ac.il/tecs/

В настоящее время я нахожусь в разделе, где excersize должен создать компилятор для очень простого языка, похожего на Java. В книге всегда говорится , что требуется, но не то, как, как (что хорошо). Я должен также упомянуть, что в нем говорится о yacc и lex и, в частности, говорится, чтобы они не использовались для проектов, описанных в книге, ради самостоятельного обучения.

Я в главе 10, которая и начинает писать токенизатор.

1) Может ли кто-нибудь дать мне общий совет - является ли регулярное выражение лучшим подходом для токенизации исходного файла?

2) Я хочу удалить комментарии из исходных файлов перед синтаксическим анализом - это не сложно, но большинство компиляторов сообщают вам строку, в которой происходит ошибка, если я просто удалю комментарии, это испортит счетчик строк, есть ли какие-то стратегии для сохранения количества строк при удалении мусора?

Заранее спасибо!

Answer 1

Сам токенизатор обычно пишется с использованием большой таблицы DFA, которая описывает все возможные допустимые токены (например, токен может начинаться с буквы, за которой следуют другие буквы / цифры, за которыми следует не буква, или с цифры, за которой следует другие числа и либо не число / точка, либо точка, за которой следует хотя бы 1 цифра, а затем не цифра и т. д. и т. д.). Я построил мой способ - идентифицировать все регулярные выражения, которые примет мой токенизатор, преобразовать их в DFA и объединить их.

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

изменить для Теория DFA :

Каждое регулярное выражение может быть преобразовано (и преобразовано) в DFA по соображениям производительности. Это удаляет любой возврат в разборе их. Эта ссылка дает вам представление о том, как это делается. Сначала вы преобразуете регулярное выражение в NFA (DFA с обратным отслеживанием), затем удаляете все узлы обратного отслеживания, раздувая конечные автоматы.

Еще один способ создать DFA вручную - это использовать здравый смысл. Возьмем, к примеру, конечные автоматы, которые могут анализировать либо идентификатор, либо число. Этого, конечно, недостаточно, поскольку вы, скорее всего, тоже захотите добавить комментарии, но это даст вам представление о базовых структурах.

          A-Z       space
->(Start)----->(I1)------->((Identifier))
     |         | ^
     |         +-+
     |        A-Z0-9
     |
     |          space   
     +---->(N1)---+--->((Number)) <----------+
      0-9  | ^    |                          |
           | |    | .       0-9       space  |
           +-+    +--->(N2)----->(N3)--------+
           0-9                   | ^
                                 +-+
                                 0-9

В некоторых примечаниях по используемой системе обозначений DFA начинается с узла (Start) и перемещается по стрелкам при считывании входных данных из вашего файла. В любой момент он может соответствовать только ОДНОМУ пути. Любые пропущенные пути по умолчанию устанавливаются на узел «ошибка». ((Number)) и ((Identifier)) - ваши конечные, успешные узлы. Оказавшись в этих узлах, вы возвращаете свой токен.

Итак, с самого начала, если ваш токен начинается с буквы, он ДОЛЖЕН продолжать набор букв или цифр и заканчиваться пробелом (пробелы, новые строки, табуляции и т. Д.). Обратного отслеживания не происходит, если это не удается, процесс токенизации завершается неудачно, и вы можете сообщить об ошибке. Вы должны прочитать книгу теории восстановления после ошибок, чтобы продолжить анализ, это действительно огромная тема.

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

Теперь для разбора скорости это преобразуется в таблицу DFA со всеми узлами на вертикальной и горизонтальной линиях. Примерно так:

             I1            Identifier  N1      N2      N3      Number
start        letter        nothing     number  nothing nothing nothing
I1           letter+number space       nothing nothing nothing nothing
Identifier   nothing       SUCCESS     nothing nothing nothing nothing
N1           nothing       nothing     number  dot     nothing space
N2           nothing       nothing     nothing nothing number  nothing
N3           nothing       nothing     nothing nothing number  space
Number       nothing       nothing     nothing nothing nothing SUCCESS

То, как вы это запустите, заключается в том, что вы сохраняете свое начальное состояние и перемещаетесь по таблице, читая вводимые символы за символом. Например, вход «1.2» будет обрабатываться как start-> N1-> N2-> N3-> Number-> SUCCESS. Если в какой-то момент вы нажмете на «ничто», у вас будет ошибка.

edit 2: таблица должна быть на самом деле узлом-> символом-> узлом, а не узлом-> узлом-> символом, но в любом случае она работала нормально. Прошло много времени с тех пор, как я последний раз писал компилятор вручную.

Answer 2

1 - Да, регулярные выражения хороши для реализации токенизатора. Если вы используете сгенерированный токенайзер, такой как lex, вы описываете каждый токен как регулярное выражение. см. ответ Марка.

2- Лексер - это то, что обычно отслеживает информацию о строках / столбцах, поскольку токены используются токенайзером, вы отслеживаете информацию о строках / столбцах с помощью токена или используете его в качестве текущего состояния. Поэтому, когда проблема обнаружена, токенизатор знает, где вы находитесь. Поэтому при обработке комментариев при обработке новых строк токенизатор просто увеличивает значение line_count.

В Lex вы также можете иметь разбор состояний. Многострочные комментарии часто реализуются с использованием этих состояний, что позволяет упростить регулярные выражения. Как только вы найдете совпадение с началом комментария, например, «/ *», вы перейдете в состояние комментария, которое вы можете настроить для исключения из обычного состояния. Поэтому, когда вы используете текст, ищущий маркер конца комментария '* /', вы не соответствуете обычным токенам.

Этот процесс на основе состояния также полезен для строковых литералов процесса, которые допускают вложенные конечные создатели, например, "test \" more text ".