И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901), страница 4
Текст из файла (страница 4)
имеютвидA → aα1 | aα2 | ... | aαn | β1 | ... |βm,где a ⊂ VT; αi,βj ⊂ (VT ∪ VN)*, то непосредственно применять РС-методнельзя. Можно преобразовать правила вывода данного нетерминала,объединив правила с общими началами в одно правило:A → aA’ | β1 | ... | βmA’ → α1 | α2 | ... | αnБудет получена грамматика, эквивалентная данной.c) если в грамматике есть нетерминал, у которого несколько правилвывода, и среди них есть правила, начинающиеся нетерминальнымисимволами, т.е. имеют видA → B1α1 | ... | Bnαn | a1β1 | ...
| amβmB1 → γ11 | ... | γ1k...Bn → γn1 | ... | γnp,где Bi ⊂ VN; aj ⊂ VT; αi, βj, γij ⊂ (VT ∪ VN)*, то можно заменить вхождениянетерминалов Bi их правилами вывода в надежде, что правилонетерминала A станет удовлетворять требованиям метода рекурсивногоспуска:A → γ11α1 | ... | γ1kα1 | ... | γn1αn | ... | γnpαn | a1β1 | ... | amβmd) если допустить в правилах вывода грамматики пустую альтернативу,т.е. правила видаA → a1α1 | ... | anαn | ε ,то метод рекурсивного спуска может оказаться неприменимым (несмотряна то, что в остальном достаточные условия применимостивыполняются).Например, для грамматики G = ({a,b}, {S,A}, P, S), гдеP: S → bAaA → aA | εРС-анализатор, реализованный по обычной схеме, будет таким:void S(void){if (c == ‘b’) {c = fgetc(fp); A();if (c != ‘a’) ERROR();}else ERROR();}void A(void){if (c == ‘a’) {c = fgetc(fp); A();}}Тогда при анализе цепочки baaa функция A() будет вызвана три раза;она прочитает подцепочку ааа, хотя третий символ а - это частьподцепочки, выводимой из S.
В результате окажется, что baaa непринадлежитязыку,порождаемомуграмматикой,хотявдействительности это не так.Проблема заключается в том, что подцепочка, следующая за цепочкой,выводимой из A, начинается таким же символом, как и цепочка,выводимая из А.Однако в грамматике G = ({a,b,с}, {S,A}, P, S), гдеP: S → bAсA → aA | εнет проблем с применением метода рекурсивного спуска.Выпишем условие, при котором ε-правило вывода делает неприменимымРС-метод.Определение: множество FIRST(A) - это множество терминальныхсимволов, которыми начинаются цепочки, выводимые из А в грамматикеG = (VT, VN, P, S), т.е. FIRST(A) = { a ⊂ VT | A ⇒ aα, A ⊂ VN,α ⊂ (VT ∪ VN)*}.Определение: множество FOLLOW(A) -это множество терминальныхсимволов, которые следуют за цепочками, выводимыми из А вграмматикеG = (VT, VN, P, S), т.е.
FOLLOW(A) = { a ⊂ VT | S ⇒ αAβ, β ⇒ aγ, A ⊂ VN, α,β, γ ⊂ (VT ∪ VN)*}.Тогда, если FIRST(A) ∩ FOLLOW(A) ≠неприменим к данной грамматике.ЕслиA → α1A | ... | αnA | β1 | ... |βm| ε, то метод рекурсивного спускаB → αAβи FIRST(A) ∩ FOLLOW(A) ≠(из-за вхождения А в правила вывода дляВ), то можно попытаться преобразовать такую грамматику:B → αA’A’ → α1A’ | ... | αnA’ | β1β | ... |βmβ| βA → α1A | ...
| αnA | β1 | ... |βm| εПолученная грамматика будет эквивалентна исходной, т.к. из B попрежнему выводятся цепочки вида α {αi} βj β либо α {αi} β.Однако правило вывода для нетерминального символа A’ будет иметьальтернативы, начинающиеся одинаковыми терминальными символами,следовательно, потребуются дальнейшие преобразования, и успех негарантирован.Метод рекурсивного спуска применим к достаточно узкому подклассу КСграмматик. Известны более широкие подклассы КС-грамматик, длякоторых существуют эффективные анализаторы, обладающие тем жесвойством, что и анализатор, написанный методом рекурсивного спуска,- входная цепочка считывается один раз слева направо и процессразбора полностью детерминирован, в результате на обработку цепочкидлины n расходуется время cn. К таким грамматикам относятся LL(k)грамматики,LR(k)-грамматики,грамматикипредшествованияинекоторые другие (см., например, [2], [3]).Синтаксический анализатор для М-языкаБудем считать, что синтаксический и лексический анализаторывзаимодействуют следующим образом: анализ исходной программы идетпод управлением синтаксического анализатора; если для продолженияанализа ему нужна очередная лексема, то он запрашивает ее улексического анализатора; тот выдает одну лексему и "замирает" до техпор, пока синтаксический анализатор не запросит следующую лексему.Соглашение1.
об используемых переменных и типах:•••пусть лексический анализатор выдает лексемы типа struct lex {intclass; int value;};при описанном выше характере взаимодействия лексического исинтаксическогоанализаторовестественносчитать,чтолексический анализатор - это функция getlex с прототипом structlex getlex (void);в переменной struct lex curr_lex будем хранить текущую лексему,выданную лексическим анализатором.1. об используемых функциях:int id (void); - результат равен 1, если curr_lex.class = 4, т.е.
curr_lexпредставляет идентификатор, и 0 - в противном случае;int num (void); - результат равен 1, если curr_lex.class = 3, т.е. curr_lexпредставляет число-константу, и 0 - в противном случае;int eq (char * s); - результат равен 1, если curr_lex представляет строкуs, и 0 - иначе ;void error(void) - функция обработки ошибки; при обнаружении ошибкиработа анализатора прекращается.Тогда метод рекурсивного спуска реализуется с помощью следующихпроцедур, создаваемых для каждого нетерминала грамматики:для P → program D' ; B⊥void P (void){if (eq ("program")) curr_lex = getlex();else ERROR();D1();if (eq (";")) curr_lex = getlex(); else ERROR();B();if (!eq ("⊥")) ERROR();}для D' → var D {; D}void D1 (void){if (eq ("var")) curr_lex = getlex();else ERROR();D();while (eq (";")){curr_lex = getlex (); D();}}для D → I {,I}: [ int | bool ]void D (void){if (!id()) ERROR();else {curr_lex = getlex();while (eq (",")){curr_lex = getlex();if (!id()) ERROR();else curr_lex = getlex ();}if (!eq (":")) ERROR();else {curr_lex = getlex();if (eq ("int") || eq ("bool"))curr_lex = getlex();else ERROR();}}}для E1 → T {[ + | - | or ] T}void E1 (void){T();while (eq ("+") || eq ("-") || eq ("or")){curr_lex = getlex(); T();}}...........Для остальных нетерминалов грамматики модельного языка процедурырекурсивного спуска пишутся аналогично."Запуск" синтаксического анализатора:...
curr_lex = getlex(); P(); ...О семантическом анализеКонтекстно-свободные грамматики, с помощью которых описываютсинтаксисязыковпрограммирования,непозволяютзадаватьконтекстные условия, имеющиеся в любом языке.Примеры наиболее часто встречающихся контекстных условий:1. каждый используемый в программе идентификатор должен бытьописан, но не более одного раза в одной зоне описания;2.
при вызове функции число фактических параметров и их типыдолжны соответствовать числу и типам формальных параметров;3. обычно в языке накладываются ограничения на типы операндовлюбой операции, определенной в этом языке; на типы левой иправой частей в операторе присваивания; на тип параметра цикла;на тип условия в операторах цикла и условном операторе и т.п.Проверку контекстных условий часто называют семантическим анализом.Его можно выполнять сразу после синтаксического анализа, некоторыетребования можно контролировать во время генерации кода (например,ограничения на типы операндов в выражении), а можно совместить ссинтаксическим анализом.Мы выберем последний вариант: как только синтаксический анализаторраспознает конструкцию, на компоненты которой наложены некоторыеограничения, проверяется их выполнение.
Это означает, что на этапесинтаксическогоанализапридетсявыполнятьнекоторыедополнительные действия, осуществляющие семантический контроль.Если для синтаксического анализа используется метод рекурсивногоспуска, то в тела процедур РС-метода необходимо вставить вызовыдополнительных "семантических" процедур (семантические действия).Причем, как показывает практика, удобнее вставить их сначала всинтаксические правила, а потом по этим расширенным правиламстроить процедуры РС-метода. Чтобы отличать вызовы семантическихпроцедур от других символов грамматики, будем заключать их в угловыескобки.Замечание: фактически, мы расширили понятие контекстно-свободнойграмматики, добавив в ее правила вывода символы-действия.Например, пусть в грамматике есть правилоA → a<D1>B<D1;D2> | bC<D3> ,здесь A,D,C ⊂ VN; a,b ⊂ VT; <Di> означает вызов семантическойпроцедуры Di, i = 1, 2, 3.
Имея такое правило грамматики, легконаписать процедуру для метода рекурсивного спуска, которая будетвыполнять синтаксический анализ и некоторые дополнительныедействия:void A() {if (c=='a') {c = fgetc(fp); D1(); B(); D1(); D2();}else if (c == 'b') {c = fgetc(fp); C(); D3();}else ERROR();}Пример: написать грамматику, которая позволит распознавать цепочкиязыка L = {α ⊂ (0,1)+⊥ | α содержит равное количество 0 и 1}.Этого можно добиться, пытаясь чисто синтаксическими средствамиописать цепочки, обладающие этим свойством. Но гораздо проще спомощью синтаксических правил описать произвольные цепочки из 0 и1, а потом вставить действия для отбора цепочек с равным количеством0 и 1:S → <k0 = 0; k1 = 0;> A⊥A → 0<k0 = k0+1>A | 1<k1 = k1+1>A |0<k0 = k0+1; check()> | 1<k1 = k1+1; check()>, гдеvoid check(){if (k0 != k1) { printf("ERROR !!!"); exit(1);}else { printf("SUCCESS !!!");exit(0);}}Теперь по этой грамматике легко построить анализатор, распознающийцепочки с нужными свойствами.Семантический анализатор для М-языкаКонтекстные условия, выполнение которых нам надо контролировать впрограммах на М-языке, таковы:1.
Любое имя, используемое в программе, должно быть описано итолько один раз.2. В операторе присваивания типы переменной и выражения должнысовпадать.3. В условном операторе и в операторе цикла в качестве условиявозможно только логическое выражение.4. Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выраженииопределяются по обычным правилам (как в Паскале).Проверку контекстных условий совместим с синтаксическим анализом.Для этого в синтаксические правила вставим вызовы процедур,осуществляющих необходимый контроль, а затем перенесем их впроцедуры рекурсивного спуска.Обработка описанийДля контроля согласованности типов в выражениях и типов выражений воператорах, необходимо знать типы переменных, входящих в этивыражения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
