![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Eli Bendersky описывает забавную особенность Cишной грамматики - контекстную зависимость, создаваемую typedef.
http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited/
В то время как примеры хороши, в особенности последний, следует заметить, что решение не очень - вместо того, чтобы так насиловать лексер и парсер, а тем более обращаться к технике GLR (не имеющей приемлемой строгой верхней оценки времени работы), существует намного лучший подход, который, насколько я припомню, использовался ещё в компиляторах Watcom - двухпроходный парсер.
Первый парсер "вгрязную" проходит по программе, проверяя симметричность расстановки скобок и собирая дерево "снизу вверх", как и положено любому YACC-парсеру. Затем дерево в собранном виде просматривается "сверху вниз" (контекстная зависимость) и по ходу идентификаторам присваиваются тэги "имя типа" или "имя переменной". Затем полученное дерево линеаризуется и уже в форме плоского потока лексем скармливается второму, "чистовому" парсеру (лексема "идентификатор" при этом уже не используется, а вместо неё используются две других лексемы - "имя типа" и "имя переменной/функции").
Этот трюк позволяет элегантно решить проблему, не прибегая к искажениям теоретической модели лексера (finite state machine), парсера (context-free grammar) и не используя экзотические средства разбора, работающие (на некоторых программах) недопустимо долго.
http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited/
В то время как примеры хороши, в особенности последний, следует заметить, что решение не очень - вместо того, чтобы так насиловать лексер и парсер, а тем более обращаться к технике GLR (не имеющей приемлемой строгой верхней оценки времени работы), существует намного лучший подход, который, насколько я припомню, использовался ещё в компиляторах Watcom - двухпроходный парсер.
Первый парсер "вгрязную" проходит по программе, проверяя симметричность расстановки скобок и собирая дерево "снизу вверх", как и положено любому YACC-парсеру. Затем дерево в собранном виде просматривается "сверху вниз" (контекстная зависимость) и по ходу идентификаторам присваиваются тэги "имя типа" или "имя переменной". Затем полученное дерево линеаризуется и уже в форме плоского потока лексем скармливается второму, "чистовому" парсеру (лексема "идентификатор" при этом уже не используется, а вместо неё используются две других лексемы - "имя типа" и "имя переменной/функции").
Этот трюк позволяет элегантно решить проблему, не прибегая к искажениям теоретической модели лексера (finite state machine), парсера (context-free grammar) и не используя экзотические средства разбора, работающие (на некоторых программах) недопустимо долго.
