Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>2010, Laura Kallmeyer, Parsing Beyond Context-Free Grammars
Начал читать, и с первого взгляда автор очень быстро уводит фокус на интерпретацию семантической модели в контексте отдельно взятого натурального языка.
Я не знаю какую задачу хотите решить вы, но в плане машинных компиляторов подобные задачи решаются уже следующими слоями, которые авляются надстройками над разобранной, примитивной, дословной семантической моделью программы.
Например, Control Flow Graph строится не граматикой (!), а уже следующим слоем, ответственным за семантическую интерпретацию инструкций. Следующий слой, Data Flow Analysis, строится поверх Control Flow Graph, и т.д.
То же самое относится к выводу типов, декомпозии синтаксического сахара и прочему так наываемому lowering'y — они все идут после грамматики и в основном сделаны на старых добрых pattern matching, if и switch.
Что-то должно идти перед грамматикой — препроцессор макросов, триграфов и пр. Но можно препроцессор сделать и после грамматики — но это тогда уже будет не C препроцессор, а нечто свое.
Я к тому, что да, известно что грамматики могут обладать Тьюринговой полнотой и на них можно строить полезные вычисления. И это действительно может иметь смысл в случае натуральных языков, но в случае классических (однозначных) машинных все в основном сводится к строгой иерархии и интерпретации, и тогде уже выгоднее использовать архитектуру слоенного торта.
Поэтому, ваш вопрос о lex и yacc требует уточнения в плане класса задач который вы хотите решать. Вы хотите написать свой компилятор? Если да, то в чем была бы его особенность? В том, что он будет использовать одну большую грамматику и вы сможете выиграть в эффективности?
Здравствуйте, Эйнсток Файр, Вы писали:
ЭФ>lex — это регулярные автоматы ЭФ>yacc — это КС-грамматики
ЭФ>но на самом деле всё не так.
ЭФ>Можно обойтись без lex, если токены будут соответствовать буквам. ЭФ>Но тогда в грамматике придётся писать правила для учёта пробельных символов, ЭФ>и грамматика станет более "зашумлённой".
А как могло быть иначе, если регулярные грамматики — это частный случай КС грамматик?
Могло бы разделение пройти по другому принципу. Из КС-грамматики можно было бы вынести МАКСИМАЛЬНО ВОЗМОЖНОЕ количество регулярных частей.
Но нет, остановились далеко не доходя до этой оптимальной точки.
Впрочем, чего я вам это рассказываю, если вы смысла написанного выше не поняли и вещаете свою собственную пропаганду?
ЭФ>Могло бы разделение пройти по другому принципу. Из КС-грамматики можно было бы вынести МАКСИМАЛЬНО ВОЗМОЖНОЕ количество регулярных частей. ЭФ>Но нет, остановились далеко не доходя до этой оптимальной точки.
Если из КС грамматики "вынести регулярные части", то это уже будет не КС грамматика.
ЭФ>lex — это регулярные автоматы ЭФ>yacc — это КС-грамматики
Всё правильно, lex описывает регулярную грамматику, а yacc — КС.
Простейшие парсеры можно и на lex написать, если регулярного языка хватает. Например, вложенных конструкций нет. И наоборот, можно выбросить lex и сразу написать грамматику в yacc, где токенами будут символы.
Так зачем же нам lex, спросите вы? Дело в том что регулярная грамматика компилируется в ДКА, который исполняется на порядки быстрее чем тот же автомат сгенерённый yacc'ом. Поэтому для скорости разбора полезно всё что можно выразить регулярным языком вынести в лексер.
