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

Question

Я прочитал в Sebesta book , что компилятор проводит большую часть своего времени в лексическом исходном коде. Таким образом, оптимизация лексера является необходимостью, в отличие от синтаксического анализатора.

Если это так, то почему этап лексического анализа занимает так много времени по сравнению с синтаксическим анализом в целом?

Под синтаксическим анализом я подразумеваю процесс деривации.

Answer 1

Во-первых, я не думаю, что это действительно так: во многих компиляторах большая часть времени не тратится на лексирование исходного кода. Например, в компиляторах C ++ (например, g ++) большая часть времени тратится на семантический анализ, в частности на разрешение перегрузки (пытаясь выяснить, какие неявные реализации шаблона следует выполнять). Кроме того, в C и C ++ большая часть времени часто тратится на оптимизацию (создание представлений графов для отдельных функций или всей единицы перевода, а затем выполнение длинных алгоритмов на этих графах).

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

Answer 2

Лексический анализ - это процесс, при котором все символы в исходном коде преобразуются в токены. Например

foreach (x in o)

читается символ за символом - "f", "o" и т. Д.

Лексический анализатор должен определять видимые ключевые слова («foreach», а не «for» и т. Д.)

К тому времени, когда происходит синтаксический анализ, программный код является «просто» серией токенов. Тем не менее, я согласен с ответом выше, что лексический анализ не обязательно является самым трудоемким процессом, просто он имеет самый большой поток для работы.

Answer 3

Раньше, конечно, лексинг был дорогим. Часть этого была связана с ограниченной памятью и выполнением нескольких файловых операций для чтения в битах программы. Теперь, когда объем памяти измеряется в ГБ, это больше не проблема, и по той же причине можно сделать гораздо больше работы, поэтому оптимизация важнее. Конечно, много ли помогает оптимизация - это другой вопрос.

Answer 4

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