Краткие ответы по теории (1115075), страница 2
Текст из файла (страница 2)
Алгоритмыудаления недостижимых и бесполезных (бесплодных) символов. Приведеннаяграмматика.Символ xÎ(VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), еслион не появляется ни в одной сентенциальной форме этой грамматики.Алгоритм удаления недостижимых символов:1. V0 = {S}; i = 12. Vi = {x | xÎ(VT È VN), в Р есть A -> axb и AÎVi-1, a, bÎ(VT U VN)*} È Vi-13. Если Vi ¹ Vi-1, то i=i+1 и переходим к шагу 2, иначе VN’ = Vi Ç VN; VT’ = Vi Ç VT; P’состоит из правил множества P, содержащих только символы Vi; G’ = (VT’, VN’, P’,S).Символ А из VN называется бесплодным в грамматике G = (VT, VN, P, S), еслимножество {aÎVT* | A -> a} пустоАлгоритм удаления бесплодных символов:Рекурсивно строим множества N0, N1, …1.
N0 = 0, i = 12. Ni = {A | (A -> a)ÎP и aÎ(Ni-1 È VT)*} È Ni-13. Если Ni ¹ Ni-1, то i=i+1 и переходим к шагу 2, иначе VN’ = Ni, P’ состоит из правилмножества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S)Грамматика называется приведенной, если в ней нет недостижимых и бесплодныхсимволов.Алгоритм приведения грамматики:1. Обнаруживаются и удаляются все бесплодные символы2. Обнаруживаются и удаляются все недостижимые символы13.
Определение недетерминированного конечного автомата (НКА).Недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где:K – конечное множество состоянийVT – конечное множество допустимых входных символовF – функция переходов: отображение множества K´VT -> KHÌК – конечное множество начальных состоянийSÌK – конечное множество заключительных состояний14.
Диаграмма состояний (ДС) конечного автомата .Диаграмма состояний (ДС) НКА – это ориентированный помеченный граф такой, что:1. Его вершины помечены символами состояний из K2. Вершины А и В соединяются дугой от А к В, если $ aÎVT: F(A,a)=B, при этом дугапомечется всеми такими а.15. Леволинейные регулярные грамматики и конечные автоматы.tHtA~A -> tA -> t~HB~B -> AtB -> At~AttAAB16. Определение детерминированного конечного автомата (ДКА).Конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где:K – конечное множество состоянийVT – конечное множество допустимых входных символовF – функция переходов: отображение множества K´VT -> KHÎК – начальное состояниеSÌK – конечное множество заключительных состоянийКонечный автомат называют детерминированным конечным автоматом (ДКА), если вкаждом из его состояний для любого входного символа функция перехода содержит неболее одного состояния: для любого а из VT и A из K: либо F(A, a) = {R}, RÎQ, либо P(a,q) = Æ17.
Алгоритм построения детерминированного конечного автомата по НКА.М = (K, VT, F, H, S) – НКА; M’ = (K’, VT, F’, H’, S’) – ДКА, допускающий тот же язык,что и М.1. Множество состояний К’ состоит из всех подмножеств множества К. Каждоесостояние из К’ будем обозначать [A1A2…An], где AiÎК2. Отображение F’ определим как F’([A1 A2…An], t) = [B1B2…Bm], где для каждого 1 £ j £m F(Ai, t) = Bj для каких-либо1£i£n3. Пусть H = {H1, H2, … Hk}, тогдa H' = [H1, H2, …, Hk]4. Пусть S = {S1, S2, …, Sp}, тогда S’ – все состояния из K’, имеющие вид […Si…], SiÎSдля какого-либо 1 £ i £ p.18.
Задачи лексического анализа.· Выделить в исходном тексте цепочку символов, представляющую лексему· Удалить пробельные символы и комментарии· Зафиксировать в специальных таблицах для хранения разных типов лексем фактпоявления соответствующих лексем в анализируемом тексте· Преобразовать цепочку символов, представляющих лексему, в пару (тип лексемы,указатель на информацию о ней)Лексический анализ важен для процесса компиляции по нескольким причинам:· Замена в программе идентификаторов, констант, ограничителей и служебных словлексемами делает представление программы более удобным для дальнейшейобработки· Лексический анализ уменьшает длину программы, устраняя из ее исходногопредставления несущественные пробелы и комментарии· Если будет изменена кодировка в исходном представлении программы, то этоотразится только на лексическом анализаторе.19.
Лексический анализ на основе регулярных грамматик.Лексемы можно описать с помощью регулярных грамматик.Например, идентификатор (I): I -> a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9; целое без знака (N):N -> 0 | 1 |...| 9 | N0 | N1 |...| N9 и т.д.Для грамматик этого класса, как мы уже видели, существует простой и эффективныйалгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этойграмматикой.
Однако перед лексическим анализатором стоит более сложная задача: ондолжен сам выделить в исходном тексте цепочку символов, представляющую лексему, атакже преобразовать ее в пару (тип_лексемы, указатель_на_информацию_о_ней). Длятого, чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммысостояний, введем на дугах дополнительный вид пометок - пометки-действия Di. Смыслпрежний - если в состоянии A очередной анализируемый символ совпадает с ti длякакого-либо i = 1, 2 ,...
n, то осуществляется переход в состояние B; при этом необходимовыполнить действия D1, D2, ... ,Dm.20. Объектная модель лексического анализатора. Схема его работы.*****21. Задачи синтаксического анализа.· Проверка правильности синтаксиса· Фиксация распознанной синтаксической структуры программы.Для описания языка программирования достаточно грамматики типа 2.Существуют алгоритмы зависимости сложности вычислений cn3, cn2.Универсального алгоритма сложности cn нет.
Есть только для формальной грамматики –метод рекурсивного спуска. Он лежит в основе многих методов, применяется к узкомуподклассу КС грамматик.22. Метод рекурсивного спуска (МРС): назначение, семантика процедур рекурсивногоспуска.Один из алгоритмов анализа входной цепочки,расходующий линейное время.Последовательность разбора эквивалентна построению дерева разбора методом «сверхувниз». Для каждого нетерминала грамматики создается своя процедура, носящая его имя,ее задача – начиная с указанного места исходной цепочки найти подцепочку, котораявыводится из этого нетерминала. Если такую подцепочку считать не удается, топроцедура завершает свою работу вызовом процедуры обработки ошибки, котораявыдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор.Если цепочку удалось найти, то работа процедуры считается нормально завершенной иосуществляет возврат в точку вызова.
Тело каждой такой процедуры пишетсянепосредственно по правилам вывода соответствующего нетерминала: для правой частикаждого правила осуществляется поиск подцепочки, выводимой из этой правой части.При этом терминалы распознаются самой процедурой, а нетерминалы соответствуютвызовам процедур, носящих их имена.23. Достаточные условия применимости метода рекурсивного спуска.· Либо A->a, где а aÎ(VN È VN)* и это единственное правило вывода для этогонетерминала· Либо A-> a1a1 | a2a2 | ¼ | anan, где aiÎVT для всех i = 1, 2, …, n; ai ¹ aj при i ¹ j;aiÎ(VN È VN)*, т. е.
если для нетерминала А правил вывода несколько, то онидолжны начинаться с терминалов, причем все эти терминалы должны бытьразличимыми.24. Исследование применимости МРС в случае наличия ε-альтернативы иитерационных правил.1. МРС заведомо не применяется, если в грамматике есть правила, заведомо нерекурсивные, т.к. постоянно обращаются к А( ). Получается зацикливание. Например,A -> Aα | βПреобразования:A -> βΒΒ -> αΒ | εПри этом В должен быть новым терминальным символом в грамматике; εобязательно, иначе преобразование не равносильно.2. Две альтернативы начинаются с одинакового терминального символа:A -> aα1 | aα2 | βТогда этот символ выносится и вводится новый нетерминальный символ.Преобразования:A -> aB | βΒ -> α1 | α23. Есть альтернативы, начинающиеся с терминальных символов.Α -> Βα | βТак как мы рассматриваем приведённые грамматики, то существует правило вида Β > γ1 | γ2 , которое раскрывает В.Преобразования:Α -> γ1α | γ2α | βсм.
пункт 2, если γ1 и γ2 начинаются с одного символа.В результате избавились от нетерминальных символов в правой части.4. Α -> Αa | β | εЭто УКС грамматика. Если есть правило с ε, метод применим не всегда.Преобразования:S -> bAaA -> aA | εvoid A( ) {if (c==’a’) { gc( ); A( ); }}Например, для цепочки baa метод неприменим: в правиле S -> bAa при выходе из А() мы должны считать a, но перед этим мы уже считали символ конца ввода, поэтомуметод неприменим.Пусть FIRST (A) – множество терминальных символов, с которых начинаются цепочки,выводимые из этого терминального символа; FOLLOW (A) – множество терминальныхсимволов, с которых начинаются подцепочки, следующие за данным нетерминальнымсимволом А.Правило: Если FIRST(A) Ç FOLLOW(A) ¹ Æ, то метод не применим, если = Æ, тогдаданное правило не влияет на применимость метода (эти множества надо считать лишьдля тех нетерминальных символов, из которых выводится ε).Пример.S -> fASd | εA -> Aa | Ab | dB | fB -> bcB | ε1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
