Описание:Рассматривается применение теории формальных языков и грамматик в практических задачах, связанных с обработкой текстов. Используются утилиты lex и и yacc. Утилита lex разбивает текст на лексемы, заданные в виде регулярных выражений, и выполняет связанные с этим действия, определенные в программе пользователя. Разбор выполняется сканером с помощью конечного автомата, построенного по набору лексем. Утилита yacc предназначена для синтаксического разбора языка, заданного контекстно-свободной грамматикой. По записи грамматики и указанным семантическим программам, связанным со свертками по правилам грамматики, утилита yacc строит парсер, которые осуществляет алгоритм разбора с помощью конечного автомата со стеком. Парсер является основной частью компилятора формального языка, он переводит текст с исходного языка в промежуточное представление (например, на язык виртуальной стековой машины либо на язык RTL, представляющий собой обобщенный Ассемблер). Затем по промежуточному представлению либо генерируется выходной код программы, либо реализуется интерпретатор, который исполняет промежуточный код непосредственно.