Системное программное обеспечение. Лабораторный практикум

Однако такая грамматика будет очень сложна для синтаксического анализа, поскольку в ней возникает проблема выбора правила между E—T и – T при выполнении свертки (можно проверить и прийти к выводу, что она, например, не является грамматикой операторного предшествования). Преобразования для этой грамматики неочевидны.

Но возможно более простое решение, если понять, как различить две операции (унарный и бинарный знаки «минус») на этапе лексического анализа. Различие можно сделать, если заметить, что бинарный минус всегда следует после операнда (переменной или константы) или после закрывающей круглой скобки, в то время как унарный минус – или после знака операции, или после открывающей круглой скобки. Такой анализ вполне по силам КА, если в него добавить еще одно состояние, которое будет определять, какую лексему (унарный или бинарный минус) сопоставлять с входным символом «—». Поскольку перед унарным минусом, как и перед любыми другими лексемами, может быть комментарий, то придется добавить два состояния (чтобы различать, в каком месте КА встретилось начало комментария, и после завершения комментария вернуться в то же место).

Таким образом, незначительное усложнение КА лексического анализатора позволит избежать серьезных проблем на этапе синтаксического анализа.

Данный пример иллюстрирует, как важно рационально провести границу между лексическим и синтаксическим анализом.

Другой пример из заданного входного языка еще более очевиден, хотя он и не ведет к столь серьезным осложнениям при лексическом разборе: это знак операции «не равно» – «<>». Его можно рассматривать как две лексемы или как одну. В первом случае проверка правильности этой операции будет идти на этапе синтаксического анализа, во втором случае – на этапе лексического анализа. Оба варианта могут быть без проблем реализованы, но второй из них представляется все же более логичным.

Как правило, если есть возможность выявления ошибки на более ранних стадиях компиляции, лучше такой возможностью воспользоваться. Из этой рекомендации есть исключения – ей лучше не следовать в тех случаях, когда ранний анализ не дает существенных преимуществ, но может нарушить логическую стройность языка или грамматики, затруднит их восприятие человеком.

Например, в том же входном языке сочетания if(и while(могут быть рассмотрены как единые лексемы (обозначим их if_ и w_l) и выявлены на этапе лексического анализа. При этом синтаксический анализатор не получает никаких преимуществ, но правила грамматики для нетерминального символа будут иметь вид:

О → if_ В) О else О | if_ В) О | begin L end | w_l B)do О | а:=Е

Логическая целостность и структура правил нарушены, так как человеку трудно воспринимать закрывающую скобку при отсутствии открывающей, а потому от такого варианта лучше отказаться (хотя окончательное решение, конечно, всегда остается за разработчиком компилятора).

В данном языке лексический анализатор всегда может однозначно определить границы лексемы, поэтому нет необходимости в его взаимодействии с синтаксическим анализатором и другими элементами компилятора.

Приняв во внимание правила и соглашения, рассмотренные для КА в лабораторной работе № 2, полностью КА можно описать следующим образом:

M(Q,Σ,δ,q₀,F):

Q = {H, C, C1, G, S, L, V, D, P1, P2, P3, P4, E1, E2, E3, I1, I2, L2, L3, L4, B1, B2, B3, B4,

B5, W1, W2, W3, W4, W5, O1, O2, D1, D2, X1, X2, X3, A1, A2, A3, N1, N2, N3, F};

Σ = А (все допустимые алфавитно-цифровые символы);

q₀ = H;

F = {F, S}.

Функция переходов (δ) для этого КА приведена в приложении 2.

Из начального состояния КА литеры «p», «e», «i», «b», «w», «o», «x», «a» и «n» ведут в начало цепочек состояний, каждая из которых соответствует ключевому слову (цепочка, начинающаяся с «e», соответствует трем ключевым словам):

• состояния P1, P2, P3, P4 – ключевому слову prog;

• состояния E1, E2, E3 – ключевым словам end и end.;

• состояния I1, I2 – ключевому слову if;

• состояния B1, B2, B3, B4, B5 – ключевому слову begin;

• состояния W1, W2, W3, W4, B5 – ключевому слову while;

• состояния E1, L2, L3, L4 – ключевому слову else;

• состояния D1, D2 – ключевому слову do;

• состояния O1, O2 – ключевому слову or;

• состояния X1, X2, X3 – ключевому слову хог;

• состояния A1, A2, A3 – ключевому слову and;

• состояния N1, N2, N3 – ключевому слову not.

Остальные литеры ведут к состоянию, соответствующему переменной (идентификатору) – V. Если в какой-то из цепочек встречается литера, не соответствующая ключевому слову, или цифра, то КА также переходит в состояние V, а если встречается граница лексемы – запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «i» или «els», которые совпадают с началом ключевых слов).