Теория компиляторов-1. Л.41 Классическая теория компиляторов Лекция 4. - презентация

1 Теория компиляторов-1. Л.41 Классическая теория компиляторов Лекция 4

2 Теория компиляторов-1. Л.42 ОПЕРАТОРНЫЕ ГРАММАТИКИ Грамматики простого предшествия Пусть дана входная цепочка символов "….RS…". Вопрос: над какой частью цепочки сначала производить операции. Понятие приоритета, основанное на системе отношений между символами: Для любой цепочки "….RS…" возможны следующие варианты: 1. Если есть правило, заканчивающееся на R, U …R, тогда можно сказать, что R > S. 2. Если есть правило, включающее в себя RS, U …RS…, тогда можно сказать, что R = S. 3. Если же есть правило, начинающееся на S, U S…, тогда можно сказать, что R < S. S. 2. Если есть правило, включающее в себя RS, U …RS…, тогда можно сказать, что R = S. 3. Если же есть правило, начинающееся на S, U S…, тогда можно сказать, что R < S.">

3 Теория компиляторов-1. Л.43 Алгоритм разбора Стек операторов OP и стек аргументов ARG. S - верхний символ в стеке операторов OP, R – входной символ. 1.Если R – идентификатор, то поместить его в ARG и пропустить шаги 2,3. 2.Если f(S)

4 Теория компиляторов-1. Л.44 Пример разбора (a*b/c+d)*e#

5 Теория компиляторов-1. Л.45 Алгоритм Дейкстры Дано: E E + T | E – TE T T T * F | T / FT F F F ^ PF P P (E)P a Каждой операции ставится в соответствие некоторый приоритет: P(+, -)=2,P(*, /)=3, P(^) =4 АЛГОРИТМ Проверяется очередной символ во входной строке. Если это операнд, то он передается в выходную строку. Если это открывающая скобка, то она заносится в стек с приоритетом нуль. Если это операция, то ее приоритет сравнивается с приоритетом операции, находящейся на вершине стека. Если приоритет новой операции больше, то эта новая операция заносится в стек. В противном случае берется операция с вершины стека и помещается в выходную строку, после этого повторяется сравнение с новыми верхними элементами стека до тех пор, пока на вершине стека не окажется операция с приоритетом, меньшим, чем у текущей операции, или пока стек не станет пустым. После этого текущая операция заносится в стек. Если текущий символ во входной строке является закрывающей скобкой, то операции из стека последовательно переносятся в выходную строку до тех пор, пока на вершине стека не появится открывающая скобка; эта открывающая скобка отбрасывается. Если выражение закончилось, то из стека последовательно переносятся в выходную строку все оставшиеся в нем операции.

6 Теория компиляторов-1. Л.46 МАТРИЦЫ ПЕРЕХОДОВ Грамматики высокоуровневых конструкций прогр ::= инстр инстр ::= инстр; инстр инстр ::= перем := выр инстр ::= if выр then инстр else инстр end инстр ::= while выр do инстр end выр ::= выр перем | перем перем ::= i d := 10; a := b+c-d; if a then d := 1 else while d do e := e-1 end

7 Теория компиляторов-1. Л.47 Алгоритм. Исходные данные ::= ::= IF THEN ::= := ::= + | ::= i стек, переменная, хранящая текущий считываемый символ R, и переменная U, в которой будет храниться значение последней приведенной формы. 1.Стек хранит головы правил - правые части правил грамматики, заканчивающиеся терминалом. 2.Строки матрицы переходов соответствуют тем головам, которые могут появиться в стеке 3.Столбцы соотносятся с терминальными символами, включая #. 4.Элементами матрицы будут номера или адреса подпрограмм.

8 Теория компиляторов-1. Л.48 Подпрограммы 1.IF U '' THEN ERROR(1); PUSH(R); SCAN(). 2.IF U '' THEN ERROR(2); POP(); U := ' '. 3.IF U ' ' AND U ' ' THEN ERROR(3); PUSH(' +') U := ''; SCAN(). 4.IF U ' ' THEN ERROR(4); POP(); U := ' '. 5.IF U ' ' AND U ' ' THEN ERROR(5); STOP(). 6.IF U ' ' THEN ERROR(6); PUSH(' :=') U := ''; SCAN(). 7.IF U ' ' THEN ERROR(7); POP(); U := ' '. 8.IF U ' ' AND U ' ' THEN ERROR(8); POP(); U := ' '. 9.IF U ' ' AND U ' ' THEN ERROR(9); PUSH('IF THEN') U := ''; SCAN(). 10.ERROR(10); STOP(). ::= ::= IF THEN ::= := ::= + | ::= i