Разработка компиляторов
Использование грамматик для лексического анализа
Нетрудно заметить, что большинство распознаваемых лексем носят четко заданную структуру и потому возникает естественное желание применить к задаче лексического анализа теорию языков, т.е. описать с помощью какого-либо формализма характер цепочек, принимаемых на вход, а затем автоматически сгенерировать по этому описанию лексический анализатор.
Действительно, легко выписать, например, праволинейную грамматику для распознавания идентификаторов:
letter -> 'a'..'z' | 'A'..'Z' | '_' digit -> '0'..'9' ident -> letter | letter tail tail -> letter | digit | letter tail | digit tail
Как мы уже видели, по такой грамматике можно сгенерировать конечный автомат, который распознавал бы правильно сформированные идентификаторы.
Однако исторически сложилось, что для описания лексических свойств чаще используется другой формализм - регулярные выражения, к рассмотрению которых мы сейчас и перейдем.
