Разработка компиляторов
Задача определения языка
Одна из первых задач, возникающих в процессе компиляции - это определение рассматриваемого языка программирования. При рассмотрении языков, состоящих из конечного множества цепочек, проще всего явным образом перечислить все допустимые входные цепочки. Но что делать с языками, не вводящими никаких ограничений на длину входной цепочки? Для потенциально бесконечных языков нам потребуется ввести какой-то конструктивный способ описания, который позволит нам задать правила, описывающие порождаемый ими язык. Такое описание должно удовлетворять некоторым свойствам:
- Само описание должно иметь конечную длину
- Для данного описания языка должен существовать алгоритм, который мог бы проверить принадлежность некоторой входной цепочки языку
Существует целый ряд математических формализмов, в той или иной степени удобных для задания языков - вообще, этап анализа входной программы наиболее разработан и лучше всего поддержан математическими теориями. Наиболее распространенным механизмом являются грамматики, которые задают все подходящие цепочки языка с помощью некоторых порождающих правил. Очевидное достоинство грамматик заключается в том, что существует множество систем, которые по заданной грамматике генерируют программу, проверяющую соответствие входной цепочки определяемому языку. Более того, полезную работу синтаксического анализатора (например, построение дерева разбора) можно проводить параллельно с самим распознаванием языка.
Другая часто используемая идея заключается в том, что создается некоторый обобщенный алгоритм, проверяющий за конечное число шагов принадлежность данной цепочки языку. Такой алгоритм либо останавливается после конечного числа шагов и говорит "да", либо останавливается и говорит "нет". Теоретически, нас могло бы устроить и зацикливание алгоритма на неподходящих входных цепочках, но на практике такое поведение не совсем удобно.
