И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901), страница 3
Текст из файла (страница 3)
Дана регулярная грамматика с правилами:S → S0 | S1 | P0 | P1P → N.N → 0 | 1 | N0 | N1 .Построить по ней диаграмму состояний и использовать ДС для разборацепочек : 11.010 , 0.1 , 01. , 100 . Какой язык порождает эта грамматика?34. Дана ДС.1. Осуществить разбор цепочек 1011 , 10+011 и 0-101+1 .2. Восстановить регулярную грамматику, по которой была построенаданная ДС.3. Какой язык порождает полученная грамматика ?35.
Пусть имеется переменная c и функция gc(), считывающая в сочередной символ анализируемой цепочки. Дана ДС с действиями:1. Определить, что будет выдано на печать при разборе цепочки1+101//p11+++1000/5 ?2. Написать на Си анализатор по этой ДС.36. Построить регулярную грамматику, порождающую языкL = {(abb)k⊥| k ≥ 1},по ней построить ДС, а затем по ДС написать на Си анализатор для этогоязыка.37.
Построить ДС, по которой в заданном тексте, оканчивающемся на ⊥,выявляются все парные комбинации <>, <= и >= и подсчитывается ихобщее количество.38. Дана регулярная грамматика:S → A⊥A → Ab | Bb | bB → AaОпределить язык, который она порождает; построить ДС; написать на Сианализатор.39. Написать на Си анализатор, выделяющий из текста вещественныечисла без знака (они определены как в Паскале) и преобразующий их изсимвольного представления в числовое.40.
Даны две грамматики G1 и G2.G1: S → 0C | 1B | ε G2: S → 0D | 1BB → 0B | 1C | εC → 0C | 1CB → 0C | 1CC → 0D | 1D | εD → 0D | 1DL1 = L(G1);L2 = L(G2).Построить регулярную грамматику для:1. L1 L22. L1 L2Еслиразборпонейоказалсянедетерминированным,найтиэквивалентную ей грамматику, допускающую детерминированныйразбор.41.
Написать леволинейную регулярную грамматику, эквивалентнуюданной праволинейной, допускающую детерминированный разбор.a) S → 0S | 0B b) S → aA | aB | bAB → 1B | 1CA → bSC → 1C | ⊥S → aBc)B → aS | bB | ⊥d)S → 0BB → aC | aD | dBC → aBB → 1C | 1SC→⊥D→⊥42. Для данной грамматики1.2.3.4.определить ее тип;какой язык она порождает;написать Р-грамматику, почти эквивалентную данной;построить ДС и анализатор на Си.S0S | S0 | DD → DD | 1A | εA → 0B | εB → 0A | 043. Написать анализатор по следующей грамматике:a) S → C⊥ b) S → C⊥B → B1 | 0 | D0C → B1 | C1D → D0 | 0C → B1B → 0 | D0D → B1S → A0c)A → A0 | S1 | 044.
Грамматика G определяет язык L=L1∪L2, причем L1 ∩L2 = .Написать регулярную грамматику G1, которая порождает язык L1*L2 (см.задачу 20). Для нее построить ДС и анализатор.S → 0A | 1SA → 0A | 1BB → 0B | 1B | ⊥45. Даны две грамматики G1 и G2, порождающие языки L1 и L2.Построить регулярные грамматики для1. L1L22. L1L23.
L1 * L2 (см. задачу 20)G1:S → 0B | 1SB → 0C | 1B | εC → 0B | 1SG2:S → B⊥A → B1 | 0B → A1 | C1 | B0 | 1C → A0 | B1Для грамматики b) построить ДС и анализатор.46 По данной грамматике G1 построить регулярную грамматику G2 дляязыка L1* L1 (см. задачу 20), где L1 = L(G1); по грамматике G2 - ДС ианализатор.G1: S → 0S | 0BB → 1B | 1CC → 1C | ε47. Написать регулярную грамматику, порождающую язык:1. L = {ω | ω{0,1}* , где за каждой 1 непосредственно следует0};2.
L = {1ω1| ω{0,1}+ , где между вхождениями 1 нечетноеколичество 0};по ней построить ДС, а по ДС написать на Си анализатор.48. Построить лексический блок (преобразователь) для кода Морзе.Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. ....- ⊥). Выходом являются соответствующие буквы, цифры и знакипунктуации. Особое внимание обратить на организацию таблицы.Синтаксический и семантический анализНа этапе синтаксического анализа нужно установить, имеет ли цепочкалексем структуру, заданную синтаксисом языка, и зафиксировать этуструктуру.
Следовательно, снова надо решать задачу разбора: данацепочка лексем, и надо определить, выводима ли она в грамматике,определяющей синтаксис языка. Однако структура таких конструкцийкак выражение, описание, оператор и т.п., более сложная, чем структураидентификаторов и чисел. Поэтому для описания синтаксиса языковпрограммирования нужны более мощные грамматики, чем регулярные.Обычно для этого используют укорачивающие контекстно-свободныеграмматики (УКС-грамматики), правила которых имеют вид Aα, где AVN, α(VTVN)*. Грамматики этого класса, с одной стороны,позволяют достаточно полно описать синтаксическую структуруреальных языков программирования; с другой стороны, для разныхподклассовУКС-грамматиксуществуютдостаточноэффективныеалгоритмы разбора.С теоретической точки зрения существует алгоритм, который по любойданной КС-грамматике и данной цепочке выясняет, принадлежит лицепочка языку, порождаемому этой грамматикой.
Но время работытакогоалгоритма(синтаксическогоанализасвозвратами)экспоненциально зависит от длины цепочки, что с практической точкизрения совершенно неприемлемо.Существуют табличные методы анализа ([3]), применимые ко всемуклассу КС-грамматик и требующие для разбора цепочек длины nвремени cn3 (алгоритм Кока-Янгера-Касами) либо cn2 (алгоритм Эрли).Их разумно применять только в том случае, если для интересующего насязыка не существует грамматики, по которой можно построитьанализатор с линейной временной зависимостью.Алгоритмы анализа, расходующие на обработку входной цепочкилинейное время, применимы только к некоторым подклассам КСграмматик.
Рассмотрим один из таких методов.Метод рекурсивного спускаПример: пусть дана грамматика G =({a,b,c,P: S → AB⊥}, {S,A,B}, P, S), гдеA → a | cAB → bAи надо определить, принадлежит ли цепочка caba языку L(G).Построим вывод этой цепочки:S → AB⊥ → cAB⊥ → caB⊥ → cabA⊥ → caba⊥Следовательно, цепочка принадлежит языку L(G). Последовательностьприменений правил вывода эквивалентна построению дерева разбораметодом "сверху вниз":Метод рекурсивного спуска (РС-метод) реализует этот способпрактически "в лоб": для каждого нетерминала грамматики создаетсясвоя процедура, носящая его имя; ее задача - начиная с указанногоместа исходной цепочки найти подцепочку, которая выводится из этогонетерминала.
Если такую подцепочку считать не удается, то процедуразавершает свою работу вызовом процедуры обработки ошибки, котораявыдает сообщение о том, что цепочка не принадлежит языку, иостанавливает разбор. Если подцепочку удалось найти, то работапроцедуры считается нормально завершенной и осуществляется возвратв точку вызова. Тело каждой такой процедуры пишется непосредственнопо правилам вывода соответствующего нетерминала: для правой частикаждого правила осуществляется поиск подцепочки, выводимой из этойправой части.
При этом терминалы распознаются самой процедурой, анетерминалы соответствуют вызовам процедур, носящих их имена.Пример: совокупность процедур рекурсивного спуска для грамматики G= ({a,b,c,⊥}, {S,A,B}, P, S), гдеS → AB⊥P:A → a | cAB → bAбудет такой:#include <stdio.h>int c;FILE *fp; /* указатель на файл, в котором находитсяанализируемая цепочка */void A();void B();void ERROR(); /* функция обработки ошибок */void S() {A(); B();if (c != '⊥') ERROR();}void A() {if (c=='a') c = fgetc(fp);else if (c == 'c') {c = fgetc(fp); A();}else ERROR();}void B() {if (c == 'b') {c = fgetc(fp); A();}else ERROR();}void ERROR() {printf("ERROR !!!"); exit(1);}main() {fp = fopen("data","r");c = fgetc(fp);S();printf("SUCCESS !!!"); exit(0);}О применимости метода рекурсивного спускаМетод рекурсивного спуска применим в том случае, если каждое правилограмматики имеет вид:1.
либо Aα, где α(VTVN)* и это единственное правиловывода для этого нетерминала;2. либо Aa1α1 | a2α2 | ... | anαn, где aiVT для всех i = 1,2,...,n; ai≠ aj для i ≠ j; αi(VTVN)*, т. е. если для нетерминала А правилвывода несколько, то они должны начинаться с терминалов,причем все эти терминалы должны быть различными.Ясно, что если правила вывода имеют такой вид, то рекурсивный спускможет быть реализован по выше изложенной схеме.Естественно, возникает вопрос: если грамматика не удовлетворяет этимусловиям, то существует ли эквивалентная КС-грамматика, для которойметод рекурсивного спуска применим? К сожалению, нет алгоритма,отвечающего на поставленный вопрос, т.е. это алгоритмическинеразрешимая проблема.Изложенные выше ограничения являются достаточными, но ненеобходимыми.
Попытаемся ослабить требования на вид правилграмматики:(1) при описании синтаксиса языков программирования частовстречаются правила, описывающие последовательность однотипныхконструкций,отделенныхдруготдругакаким-либознакомразделителем (например, список идентификаторов при описаниипеременных, список параметров при вызове процедур и функций и т.п.).Общий вид этих правил:L → a | a,L (либо в сокращенной форме L → a {,a})Формально здесь не выполняются условия применимости методарекурсивного спуска, т.к.
две альтернативы начинаются одинаковымитерминальными символами.Действительно, в цепочке a,a,a,a,a из нетерминала L может выводитьсяи подцепочка a , и подцепочка a,a , и вся цепочка a,a,a,a,a. Неясно,какую из них выбрать в качестве подцепочки, выводимой из L. Еслипринять решение, что в таких случаях будем выбирать самую длиннуюподцепочку (что и требуется при разборе реальных языков), то разборстановится детерминированным.Тогда для метода рекурсивного спуска процедура L будет такой:void L(){ if (c != 'a') ERROR();while ((c = fgetc(fp)) == ',')if ((c = fgetc(fp)) != 'a') ERROR();}Важно, чтобывыводимых из L,запятой), иначецепочки, котораянетерминалом B S → LB⊥L → a {, a}B → ,bподцепочки, следующие за цепочкой символов,не начинались с разделителя (в нашем примере - спроцедура L попытается считать часть исходнойне выводится из L. Например, она может порождаться”соседом” L в сентенциальной форме, как в грамматикеЕсли для этой грамматики написать анализатор, действующий РСметодом, то цепочка а,а,а,b будет признана им ошибочной, хотя вдействительности это не так.Нужно отметить, что в языках программирования ограничителемподобных серий всегда является символ, отличный от разделителя,поэтому подобных проблем не возникает.(2) если грамматика не удовлетворяет требованиям применимостиметода рекурсивного спуска, то можно попытаться преобразовать ее, т.е.получить эквивалентную грамматику, пригодную для анализа этимметодом.a) если в грамматике есть нетерминалы, правила вывода которыхлеворекурсивны, т.е.
имеют видA → Aα1 | ... | Aαn | β1 | ... | βm,где αi ⊂ (VT ∪ VN)+, βj ⊂ (VT ∪ VN)*, i = 1,2,...,n; j =1,2,...,m, тонепосредственно применять РС-метод нельзя.Левую рекурсию всегда можно заменить правой:A → β1A’ | ... | βmA’A’ → α1A’ | ... | αnA’ | εБудет получена грамматика, эквивалентная данной, т.к. из нетерминалаA по-прежнему выводятся цепочки вида βj {αi}, где i = 1,2,...,n; j =1,2,...,m.b) если в грамматике есть нетерминал, у которого несколько правилвывода начинаются одинаковыми терминальными символами, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
