В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 12
Текст из файла (страница 12)
Затем этодерево можно будет использовать каким-то образом, чтобы как-то интерпретироватьвыражение языка. Если на вход будет подано грамматически ошибочное выражение, то наопределенном этапе возникнет ситуация, когда ни одно из правил разбора не будетприменимо – в этот момент можно зафиксировать ошибку синтаксиса.Грамматикаесливыражению,называетсядетерминированной,каждомусоответствующему этой грамматике, соответствует единственное дерево разбора.Приведем пример практического использования формальной грамматики – разборарифметических выражений.Построим для начала самую простую грамматику («плохую» с точки зрения разбора)(изначально уже определены понятия <имя> и <константа>)<выражение> ::= <имя> | <константа> | <выражение> <операция> <выражение><операция> ::= +|-|*|/Эта грамматика совершенно корректно описывает все арифметические выражения впределах 4х действий без скобок. Но использовать ее для разбора оказываетсяпроблематично – не учитывается приоритет операций.
Кроме того, она не являетсядетерминированной – возможны несколько равноправных деревьев разбора. Поэтомуприведем более полезную грамматику<выражение> ::= <терм> | <выражение> <+-> <терм>Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год38<терм> ::= <множитель> | <терм> <*/> <множитель><множитель> ::= <имя> | <константа> | (<выражение>)<+-> ::= +|<*/> ::= *|/Эта грамматика является детерминированнойскобки в арифметических выражениях.Приведем пример:и учитывает приоритет действий и7+5*a*(b-3) - <выражение>7 - <выражение>5*a*(b-3) - <терм>7 - <константа>5*a - <терм>(b-3) - <множитель>5 - <терм>a - <множитель>5 - <множитель>5 - <константа>a - <имя>b - <выражение>3 - <терм>3 - <константа>3 - <множитель>b - <терм>b - <множитель>b - <имя>b-3 - <выражение>По этому дереву можно, например, вычислить значение выражения при a = 5, b= -3:-143 (+)7-150 (*)725 (*)-65555-3 (b)-6 (-)5 (a)-3333-3-3(в скобках приведены операции над левым и правым операндами).
Легко видеть, чтовычисленное значение - -143 было найдено корректно.Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год39При достаточно хорошо сформулированной грамматике дерево разбора строитсяединственным образом и выражение можно свободно разбирать, проходя по нему справаналево несложным алгоритмом.
Для формализации этого вводят понятие LR-грамматики иLR-разбораLR-грамматика (от Left-Recursive – леворекурсивная), - грамматика в НФБН в которойпри разборе метасимволов рекурсия встречается только в левой части выражения и не болееодного раза. Например,<выражение> ::= <терм> | <выражение> <+-> <терм>подходит под LR-грамматику, а вот<выражение> ::= <терм> | <терм> <+-> <выражение>уже нет – рекурсия стоит в правой части<выражение> ::= <терм> | <выражение> <+-> <выражение>- тоже нет – рекурсия встречается 2 разаВыражения, записанные в LR-грамматике допускают однозначный разбор в виде дерева(т.е.
LR-грамматика является детерминированной). Для этих целей используют процедуруLR разбора:Идти по выражению слева направо, строя цепочку метасимволов – поначалутерминальных. Как только цепочку можно «свернуть» в один метасимвол – сразусворачивать и поступать так до тех пор, пока все выражение не будет свернуто в одинметасимвол. Легко видеть, что процедура свертки аналогична построению дерева разбора.Грамматика называется LR(K) – грамматикой, если для принятия решения о сверткедостаточно знать следующие K символов за текущим. Разбор в LR(K) грамматикеназывается LR(K)-разбором.
К примеру, приведенная выше грамматика разбораарифметических выражений не является LR(0)-грамматикой, т.к. нам недостаточно дляразбора знания только одного текущего метасимвола – нужен еще хотя бы один следующий.Но вот LR(1) грамматикой она является корректной. Приведем процедуру LR(1) разбораарифметических выражений.Процедура разбора строится в несколько этапов:1. Лексический разбор2. Синтаксический разбор3.
Семантический разборНа вход компилятора, осуществляющего разбор, подается последовательность символовалфавита языка (в нашем случае – из {0, 1, 2… 9, a, b, …, z, +, -, (, )}). Первый этап разбора(лексический) – выделение во входной последовательности заранее заданных терминальныхметасимволов, в нашем примере – имен и констант. После этой стадии выражение7+5*a*(b-3)будет представлено как<константа>+<константа>*<имя>*(<имя>-<константа>)Если во входном выражении встретится непонятный метасимвол (12a, например) либосимвол не из алфавита языка – то получаем лексическую ошибку.Второй и третий этапы друг от друга при LR-разборе практически неразделимы.Вообще, синтаксический разбор – построение дерева разбора, семантический – проведениевычислений (более общо – некоторых действий с деревом) по этому дереву, но при LRразборе дерево разбора в явном виде не строится и обычно сразу производится вычислениепо этому дереву – этапы не разделены ни во времени ни в «пространстве».Итак, для LR(K) разбора заводится специальный стек метасимволов.
В начале разборастек пуст. Затем разбор идет специальной программой – LR(K)-парсером с использованиемдвух операций – сдвига и свертки1.Операция сдвига: добавляем в стек очередной метасимвол из входнойпоследовательности2.Операция свертки: выбираем фрагмент стека от какого-то метасимвола и доконца и на основе следующих K символов (как стека, так и входнойпоследовательности) производим одну из сверток.Лекции по ЭВМ. Конспект. Лектор В.Д.
Валединский.Группа 208, 3 семестр, 2002 год40К сожалению, сказать, в какой последовательности необходимо выполнять эти простыеоперации по НФБН нельзя. Дело в том, что необходимо строить некоторую специальнуютаблицу всех возможных текущих состояний LR-парсера (имеющую большие размеры инетривиальное построение) и действий, которые в каждом из состояний долженпредпринимать парсер (какое из правил применять и в какое состояние переходить) наоснове еще непрочитанных метасимволов (K метасимволов для LR(K) разбора).
LR-разборпо такой таблице проходит максимально быстро, но выписывание самой таблицы выходит запределы прочитанного курса (почитать более подробно можно по ссылкамhttp://mech.math.msu.su/~vvb/2course/lect12.htmlиhttp://geonic.net/lib/development/prog/compiler/lectcomp.txt). Вручную такие таблицы никто невыписывает – для этих целей существуют специальные компиляторы компиляторов,например YACC (Yet Another Compiler Compiler), создающего по входному метаязыку(близкому к НФБН) программу на C, осуществляющую LR-разбор. Со слов К.Ю.Богачевадля языка C генерируемая программа имеет вид switch-а килобайт на 200.Поэтому мы ограничимся просто парой дополнительных замечаний о разбореарифметических выражений.Для начала – несколько слов о записи выражений.
Привычная нам форма – инфиксная,когда знак операции записывается между операндами. Однако при работе со стеком удобнееоказываются другие записи – префиксная, когда знак операции записывается передоперандами и постфиксная (ее еще называют обратной польской) – знак операцииуказывается после операндов. Пример:a*b+c*(d-e) инфиксная запись* a b + *c - d e префиксная записьa b * c d e - * + постфиксная записьПоначалу префиксная и постфиксная записи могут показаться непонятными, но ониочень удобны при вычислении выражений с использованием стека (в данных примерахследует считать, что начало стека – слева). Наиболее удобной является постфиксная запись,она наиболее часто и используется. В постфиксной записи не требуется при вычисленияхдумать о приоритетах операций и скобках – все делается автоматически.
Действительно,пусть у нас в стеке лежит выражение, записанное в постфиксной записи. Заведемдополнительный стек – чисел и начнем вычисления1.Если стек выражения пуст, стек чисел содержит только одно число – товозвращаем это число в качестве ответа, если стек чисел содержит более одногочисла – возвращаем ошибку в выражении2.Извлекаем из стека выражения очередной элемент.
Если это число – складываемего в стек чисел. Если операция – извлекаем из стека чисел нужное числооперандов, проводим над ними операцию и результат помещаем обратно в стекчисел. Если в стеке не хватает нужного числа операндов – возвращаем ошибку ввыражении. После этого возвращаемся к шагу 1.Пример разбора:шагстек выражениястек чисел1ab*cde-*+2b*cde-*+a3*cde-*+ab4cde-*+(a*b)5de-*+(a*b) c6e-*+(a*b) c d7-*+(a*b) c d e8*+(a*b) c (d-e)9+(a*b) (c*(d-e))10(a*b)+(c*(d-e))Результатом вычислений станет a*b+c*(d-e) – как мы и заказывали. Взяв конкретныеa,b,c,d,e мы бы вычислили значение выражения.Лекции по ЭВМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
