Добавил:

Studfiles2 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Предмет:

Теория языков программирования

Файл:

Курсовая работа по дисциплине Формальные языки, грамматики и автоматы / Начало.doc

Скачиваний:

Добавлен:

01.05.2014

Размер:

468.99 Кб

Скачать

☆

<<< < Предыдущая 12 / 82 3 4 5 6 7 8 > Следующая >>>

2.2. Су-схема и транслирующая грамматика

Синтаксически управляемой схемой(СУ-схемой) называется множество, состоящее из пяти объектов:T ={V_a, V_твх, V_твых, R, }, где:

V_a- множество нетерминальных символов;

V_твх- множество терминальных символов, используемых для построения входных

цепочек;

V_твых- множество терминальных символов, используемых для построения выходных цепочек;

- начальный символ; Va;

R- множество правил вида <A>,; где:

<A>V_a,(V_aU V_твх)*,(V_aU V_твых)* и нетерминалы, входящие в цепочкуобразуют перестановку нетерминалов цепочки.

Приведенное определение СУ-схемы не накладывает никаких ограничений на правила, кроме необходимости совпадения нетерминалов во входной и выходной частях правила. Для построения детерминированных устройств, осуществляющих перевод цепочек, используются СУ-схемы с дополнительными ограничениями на вид правил.

В данной работе СУ-схема должна быть простой.

СУ-схема Т ={V_a, V_твх, V_твых,R, } называетсяпростой, если для каждого правила <A>,изRсоответствующих друг другу вхождения нетерминалов встречаются вив одном и том же порядке.

СУ-схема:

Входные цепочки: Выходные цепочки:

::=<Vars><Code> == <Vars>' '<Code>

<Bukva>::=a|b|c|d|e == a|b|c|d|e

<Zifra>::=0|1|2|3|4|5|6|7|8|9 == 0|1|2|3|4|5|6|7|8|9

<Const>::="'true'"|"'false'" == "'true'"|"'false'"

<Simvol>::="'a'"|"'b'"|"'c'"|"'d'"|"'e'" == "'a'"|"'b'"|"'c'"|"'d'"|"'e'"

<R1>::=$ == $

<R2>::=$ == $

<MasBool>::='<arr>'<ID>','<Chislo>'</arr>' == <ID>' ''bool'' '<Chislo>' ''RM'

<MasChar>::='<arr>'<ID>','<Chislo>'</arr>' == <ID>' ''char'' '<Chislo>' ''RM'

<ElMas>::='<earr>'<ID>','<Chislo>'</earr>' == <ID>' '<Chislo>' ''EM'

<R3>::=$ == $

<R4>::=$ == $

<R5>::=$ == $

<Operation>::='<and>'<Operand>','<Operand>'</and>' == <Operand>' '<Operand>'&'

<Operation>::='<or>' <Operand>','<Operand>'</or>' == <Operand>' '<Operand>'V'

<Operation>::='<not>'<Operand>'</not>' == <Operand>'!'

<R6>::=$ == $

Пример вывода в данной СУ-схеме.

Для примера выведем цепочку: <boolean> b1 </boolean> <ass> b1 <not> ’false’ </not> </ass>

( , )  (<Vars><Code> , < Vars >’ ‘<Code >) 

( <boolean><NamesBool></boolean><R3><Code> , <NamesBool><R3>’ ‘<Code> ) 

( <boolean><ID><R4></boolean><R_3><Code> , <ID>‘ ‘‘bool’<R4><R3>’ ‘<Code> ) 

( <boolean>b1<R4></boolean><R3><Code> , b1‘ ‘‘bool’<R4><R3>’ ‘<Code> ) 

( <boolean>b1</boolean><R3><Code> , b1’ ’’bool’<R3>’ ‘<Code> ) 

( <boolean>b1</boolean><Code> , b1’ ’’bool’’ ‘<Code> ) 

( <boolean>b1</boolean><ass><Perem>’,‘<Vyrazh></ass><R6> ,

b1‘ ‘‘bool’‘ ‘<Perem>‘ ‘<Vyrazh>’=’<R6>) 

( <boolean>b1</boolean><ass><ID>’,‘<Vyrazh></ass><R6> ,

b1‘ ‘‘bool’‘ ‘<ID>‘ ‘<Vyrazh>’=’<R6>) 

( <boolean>b1</boolean><ass>b1’,‘<Vyrazh></ass><R6> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘<Vyrazh>’=’<R6>) 

( <boolean>b1</boolean><ass>b1’,‘<Operation></ass><R6> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘<Operation>’=’<R6>) 

( <boolean>b1</boolean><ass>b1’,‘<not><Operand></not></ass><R6> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘<Operand>’!’’=’<R6>) 

( <boolean>b1</boolean><ass>b1’,‘<not><Const></not></ass><R6> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘<Const>’!’’=’<R6>) 

( <boolean>b1</boolean><ass>b1’ ‘<not>’false’</not></ass><R6> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘’false’’!’’=’<R6>) 

( <boolean>b1</boolean><ass>b1’ ‘<not>’false’</not></ass> ,

b1‘ ‘‘bool’‘ ‘b1‘ ‘’false’’!’’=’) 

Основой построения СУ-схем перевода является использование двух грамматик, с помощью которых осуществляется синхронный вывод входной и выходной цепочек. Построение транслирующих грамматик предполагает применение другого подхода, который предусматривает использование одной грамматики и разрешает включение как входных, так и выходных символов в каждое правило такой грамматики.

Транслирующей грамматикой(Т-грамматикой) называется КС-грамматика, множество терминальных символов которой разбито на множество входных символов и множество выходных символов.

Транслирующая грамматика:

::=<Vars># #<Code>

<Bukva>::=a#a#|b#b#|c#c#|d#d#|e#e#

<Zifra>::=0#0#|1#1#|2#2#|3#3#|4#4#|5#5#|6#6#|7#7#|8#8#|9#9#

<Const>::="'true'"#'true'#|"'false'"#'false'#

<Simvol>::="'a'"#'a'#|"'b'"#'b'#|"'c'"#'c'#|"'d'"#'d'#|"'e'"#'e'#

<R1>::=$

<R2>::=$

<MasBool>::='<arr>'<ID>','# ##bool## #<Chislo>'</arr>'# ##RM#

<MasChar>::='<arr>'<ID>','# ##char## #<Chislo>'</arr>'# ##RM#

<ElMas>::='<earr>'<ID>','# #<Chislo>'</earr>'# ##EM#

<R3>::=$

<R4>::=$

<R5>::=$

<Operation>::='<and>'<Operand>','# #<Operand>'</and>'#&#

<Operation>::='<or>' <Operand>','# #<Operand>'</or>' #V#

<Operation>::='<not>'<Operand>'</not>'#!#

<R6>::=$

Выходные символы в данной транслирующей грамматике заключены в # #.

Пример вывода в данной транслирующей грамматике.

Для примера выведем цепочку: <boolean> b1 </boolean> <ass> b1 <not> ’false’ </not> </ass>



<Vars># #<Code> 

<boolean><NamesBool></boolean><R3># #<Code> 

<boolean><ID># ##bool#<R4></boolean><R3># #<Code> 

<boolean>b#b#1#1## ##bool#<R4></boolean><R3># #<Code> 

<boolean>b#b#1#1## ##bool#</boolean><R3># #<Code> 

<boolean>b#b#1#1## ##bool#</boolean># #<Code> 