LR(1) парсер. частичный парсинг

Узнал что компиляторы парсят частично - тоесть тело функций специально пропускают и оставляют на последок.
А как они это делают? Просто если произошла свёртка заголовка функции просто пропускают всё что в { }? Или чтото есть специальное ? В драконьей книге ничего не нашёл ...

Да и возникает вопрос, если лексер в YACC и BISON передаёт последовательно лексемы парсеру то пропускать лучше ориентировавшись на лексемы а не на текст. Как так они это делают?

Всем запанее спасибо!

 

Откуда инфа?

 

к примеру такой код на C#:
class aa{

void fx(){
a+=1;
}
int a;
}
тело функций придётся пропускать

 

А, понял, когда разрешено отложить объявление идентификатора.
Ну плюсы тут конечно еще и в своём особенном седле - у них есть шаблоны которые в момент определения только формируют заготовку того во что могут быть инстанциированы, поэтому у них реально понятие парсинга кода с шаблонами становится несколько смазанным. И встроенные в класс методы эквивалентны inline и тоже существуют в немного особенном контексте - им реально разрешено ссылаться на еще не заявленные члены данных.
Ну вообще раньше в подобных случаях было еще понятие компиляции в несколько проходов - типа в первый проход как раз разрешаются подобные вот именно этому примеру вещи - устанавливается истинный состав сущностей и их типов, а потом во второй проход уже начинает собираться код после точного выяснения подобных нюансов.
Но можно и как ты предложил - встретив начало функции перейти в особый режим накидывания в её "непропарсенное еще сырое тело" встреченных лексем пока не достигнем парную закрывающую скобку. Тоже вариант, думаю его применяют тоже.

 

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

 

Да я не сильно шибкий спец, самое ёмкое из теории, что читал это SICP, а ни один ЯВУ своей разработки до победного конца не довёл. Но х/з, как то в целом из разных источников по жизни это знаю, что компиляторы бывают многопроходные, что есть разница как GCC и MSVC относятся к шаблонам так что GCC уже успевает их пропарсить в какой то особенный вид AST в то время как MSVC хранит как набор лексем - поэтому у них разнилось когда то поведение-отношение к тому как трактовать некоторые заковыристые случаи (как раз GCC уже не мог поменять выбранной структуры AST, а MSVC на лету её перестраивал в совсем другую штуку (и при этом отклонялся от стандарта!)).
Но глубоко не раскопаю тему.

 

_evil, теории по LR(1) и в гугле полно,
а вот как это дело реализуется на практике - уже большой вопрос.
Возьмите компилятор с открытым исходным кодом FASM, и в его папке "SOURCE\Parser.inc" найдёте всю практич.часть. У них и форум живой, где можно спросить общий смысл/детали у самого автора (он отзывчивый).

Насколько мне не изменяет память, он говорил про какую-то таблицу, которая создаётся при первом проходе и заполняется переменными. На сл.проходе если есть зависимости, то делается "Var-1", и проверяется на нуль на следующем, и т.д. (это в общих чертах).

Например вот обычный HelloWorld! на fasm'e, в процедуру которого передаётся аргумент в виде адреса строки для MessageBox(). Как видно из логов, даже здесь компиль делает аж 4-прохода "Passes", и это далеко не предел:

Код (ASM):

1.  
2. format   pe64 gui
3. include 'win64ax.inc'
4. entry    start
5. ;//-----------
6. section '.text' code readable executable
7. msg      db  'Тест!',0
8.  
9. proc     TestProc  ;//**********************************
10.          mov       rdx,rcx
11.          invoke    MessageBox,0,rdx,0,0
12.          ret
13. endp               ;//**********************************
14.  
15. align    8
16. start:   sub     rsp,8            ;//<----- Точка входа!
17.        fastcall  TestProc,msg
18.          invoke  ExitProcess,0
19. ;//-----------
20. section '.idata' import data readable ;writeable
21. library  kernel32,'kernel32.dll',user32,'user32.dll'
22. include 'api\kernel32.inc'
23. include 'api\user32.inc'

Ключом(-s) Fasm может сбрасывать листинги препроцессора для отладки,
но в них много лишнего, а потому без наводки автора что-то конкретное найти там трудно:
(в данном случае я получил файл *.lst размером ~8 МБ )

 

Дак как парсер работает в первом проходе когда ничего пропарсить не может? просто всё сворачивает в дочерние обьекты?

--- Сообщение объединено, 19 фев 2025 в 15:50 ---

а в следующих проходах используется какаято специальная таблица парсера ?

--- Сообщение объединено, 19 фев 2025 в 16:33 ---

Тфу ююю немного стал понимать ... получается таблица одна и таже но первый проход с ошибками но снего берутся определения типов и переменных, а потом тойже таблицей парсится уситывая эти определения ... Это так?

 

Парсер работает на этапе трансляции исходника в маш.код (препроцессинг-->трансляция-->линковка/компоновка).
Так-что после первого прохода уже имеется исполняемый код, а на втором устраняются разные ошибки типа: (1)зависимости, (2)лишние по мнению компиля участки кода, и прочая оптимизация инструкций. Именно на первом проходе и создаётся таблица парсера. На выходе из транслятора получаем объектные файлы (со своей табл.адресов), которые потом связывает между собой линкер.

 

Бывают разные по сложности в этом смысле языки.
Cи первых ревизий (еще до второго издания Кернигана-Ритчи) был заточен под однопроходность - там можно было, например, построить корректный вызов функции зная только, что она её имя существует как символ. Немного сродни ассемблеру оно было.
И на самом деле в плюсах почти любой кусок кода этому правилу тоже подчиняется - кроме обозначенного выше случая, редкое исключение из правил когда можно ссылаться на незадекларированный идентификатор. Тут вообще код строить никакой нельзя - без знания что такое a (вдруг это пользовательский класс?) выражение a = 1 может превратится во что угодно. Перегруженный operator = пользовательского класса может быть чем угодно.
Поэтому трюки с отложенным парсингом тут неизбежны. В старину обычно из-за бережливого отношения к памяти такое разрешали бы скорее всего вторым проходом - но в современности это может быть некое кустистое AST-дерево, где какие то ветки могут иметь вид "непропарсенная еще последовательность токенов".

Другие же языки могут просто требовать, что прежде чем работать с идентификатором надо его объявить - и всё, такой момент сам по себе снимется.

Разрешение символов "var - 1" к парсингу отношения не имеет - оно возможно уже после того как код скопилирован в полуготовый слепок в котором вот как раз осталось только уже полностью понимая какие корневые символы какие окончательные места в образе заняли можно теперь раскручивать окончательное вычисление символов и заполнения мест в образе где они используются - при зависимостях в определении одних символов от других это действительно потребует несколько проходов, но это совсем другие проходы - это всё уже после парсинга и генерации образа происходит в финале, когда результат окончательно фиксируется.