Добавил:

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

Вуз:

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

Предмет:

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

Файл:

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

Скачиваний:

Добавлен:

01.05.2014

Размер:

468.99 Кб

Скачать

☆

<<< < Предыдущая 1 23 / 83 4 5 6 7 8 > Следующая >>>

2.3. Функции переходов преобразователя

Для всех правил вида <A>b, где bV_твхи(V_твхUV_твыхUV_a)*, строим функции вида:

f(S,b,A)=(S,’, $), где’-зеркальное отражение цепочки.

( S, a, <bukva> ) = ( S, #a#, $ )

( S, b, <bukva> ) = ( S, #b#, $ )

( S, c, <bukva> ) = ( S, #c#, $ )

( S, d, <bukva> ) = ( S, #d#, $ )

( S, e, <bukva> ) = ( S, #e#, $ )

( S, 0, <zifra> ) = ( S, #0#, $ )

( S, 1, <zifra> ) = ( S, #1#, $ )

( S, 2, <zifra> ) = ( S, #2#, $ )

( S, 3, <zifra> ) = ( S, #3#, $ )

( S, 4, <zifra> ) = ( S, #4#, $ )

( S, 5, <zifra> ) = ( S, #5#, $ )

( S, 6, <zifra> ) = ( S, #6#, $ )

( S, 7, <zifra> ) = ( S, #7#, $ )

( S, 8, <zifra> ) = ( S, #8#, $ )

( S, 9, <zifra> ) = ( S, #9#, $ )

( S, "'true'" , <const> ) = ( S, #'true'#, $ )

( S, "'false'" , <const> ) = ( S, #'false'#, $ )

( S, "'a'" , <simvol> ) = ( S, #'a'#, $ )

( S, "'b'" , <simvol> ) = ( S, #'b'#, $ )

( S, "'c'" , <simvol> ) = ( S, #'c'#, $ )

( S, "'d'" , <simvol> ) = ( S, #'d'#, $ )

( S, "'e'" , <simvol> ) = ( S, #'e'#, $ )

( S, "<arr>" , <masbool> ) = ( S, #RM## #"</arr>"<chislo># ##bool## #","<id>, $ )

( S, "<arr>" , <maschar> ) = ( S, #RM## #"</arr>"<chislo># ##char## #","<id>, $ )

( S, "<earr>" , <elmas> ) = ( S, #EM## #"</earr>"<chislo># #","<id>, $ )

( S, "<boolean>" , <vars> ) = ( S, <r3> "</boolean>" <namesbool>, $ )

( S, "<char>" , <vars> ) = ( S, <r3> "</char>" <nameschar>, $ )

( S, "," , <r4> ) = ( S, <namesbool># #, $ )

( S, "," , <r5> ) = ( S, <nameschar># #, $ )

( S, "<ass>", <code> ) = ( S,<r6>#=#"</ass>"<vyrazh># #","<perem> , $ )

( S, "<and>", <operation> ) = ( S, #&# "</and>" <operand> # # "," <operand>, $ )

( S, "<or>" , <operation> ) = ( S, #V# "</or>" <operand> # # "," <operand>, $ )

( S, "<not>", <operation> ) = ( S, #!# "</not>" <operand>, $ )

Для всех правил вида <A>, где BVa и(V_твхUV_твыхUV_a)*, строим функции вида:f*(S,x, <A>)=(S,, $) для всехxВЫБОР(<A>_вх),

где _вх-цепочка, по-лученная изпутем удаления из нее всех выходных символов.

*( S, "<boolean>" , ) = ( S, <code> # # <vars>, $ )

*( S, "<char>" , ) = ( S, <code> # # <vars>, $ )

*( S, a, <id> ) = ( S, <R1> <bukva>, $ )

*( S, b, <id> ) = ( S, <R1> <bukva>, $ )

*( S, c, <id> ) = ( S, <R1> <bukva>, $ )

*( S, d, <id> ) = ( S, <R1> <bukva>, $ )

*( S, e, <id> ) = ( S, <R1> <bukva>, $ )

*( S, a, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, b, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, c, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, d, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, e, <R1> ) = ( S, <R1> <bukva>, $ )

*( S, 0, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 1, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 2, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 3, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 4, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 5, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 6, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 7, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 8, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 9, <R1> ) = ( S, <R1> <zifra>, $ )

*( S, 0, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 1, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 2, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 3, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 4, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 5, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 6, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 7, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 8, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 9, <chislo> ) = ( S, <R2> <zifra>, $ )

*( S, 0, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 1, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 2, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 3, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 4, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 5, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 6, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 7, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 8, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, 9, <R2> ) = ( S, <R2> <zifra>, $ )

*( S, "<boolean>" , <R3> ) = ( S, <vars> # #, $ )

*( S, "<char>" , <R3> ) = ( S, <vars> # #, $ )

*( S, a, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, b, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, c, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, d, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, e, <namesbool> ) = ( S, <R4> #bool# # # <id>, $ )

*( S, "<arr>" , <namesbool> ) = ( S, <R4> <masbool>, $ )

*( S, a, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, b, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, c, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, d, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, e, <nameschar> ) = ( S, <R5> #char# # # <id>, $ )

*( S, "<arr>" , <nameschar> ) = ( S, <R5> <maschar>, $ )

*( S, a, <perem> ) = ( S, <id>, $ )

*( S, b, <perem> ) = ( S, <id>, $ )

*( S, c, <perem> ) = ( S, <id>, $ )

*( S, d, <perem> ) = ( S, <id>, $ )

*( S, e, <perem> ) = ( S, <id>, $ )

*( S, "<earr>" , <perem> ) = ( S, <elmas>, $ )

*( S, "'true'" , <vyrazh> ) = ( S, <const>, $ )

*( S, "'false'" , <vyrazh> ) = ( S, <const>, $ )

*( S, "'a'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'b'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'c'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'d'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, "'e'" , <vyrazh> ) = ( S, <simvol>, $ )

*( S, a, <vyrazh> ) = ( S, <perem>, $ )

*( S, b, <vyrazh> ) = ( S, <perem>, $ )

*( S, c, <vyrazh> ) = ( S, <perem>, $ )

*( S, d, <vyrazh> ) = ( S, <perem>, $ )

*( S, e, <vyrazh> ) = ( S, <perem>, $ )

*( S, "<earr>" , <vyrazh> ) = ( S, <perem>, $ )

*( S, "<and>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<or>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<not>" , <vyrazh> ) = ( S, <operation>, $ )

*( S, "<and>" , <operand> ) = ( S, <operation>, $ )

*( S, "<or>" , <operand> ) = ( S, <operation>, $ )

*( S, "<not>" , <operand> ) = ( S, <operation>, $ )

*( S, a, <operand> ) = ( S, <perem>, $ )

*( S, b, <operand> ) = ( S, <perem>, $ )

*( S, c, <operand> ) = ( S, <perem>, $ )

*( S, d, <operand> ) = ( S, <perem>, $ )

*( S, e, <operand> ) = ( S, <perem>, $ )

*( S, "<earr>" , <operand> ) = ( S, <perem>, $ )

*( S, "'true'" , <operand> ) = ( S, <const>, $ )

*( S, "'false'" , <operand> ) = ( S, <const>, $ )

*( S, "<ass>" , <R6> ) = ( S, <code> # #, $ )

Для всех правил вида <A>$ строим функции вида:

f*( S, x, <A>) = ( s₀, $, $ ), для всехxВЫБОР(<A>$), правило <A>$ принадлежит Г_вх.

*( S, "," , <R1> ) = ( S, $, $)

*( S, "</boolean>" , <R1> ) = ( S, $, $)

*( S, "</char>" , <R1> ) = ( S, $, $ )

*( S, "</ass>" , <R1> ) = ( S, $, $ )

*( S, "</and>" , <R1> ) = ( S, $, $ )

*( S, "</or>" , <R1> ) = ( S, $, $ )

*( S, "</not>" , <R1> ) = ( S, $, $ )

*( S, "</arr>" , <R2> ) = ( S, $, $ )

*( S, "</earr>" , <R2> ) = ( S, $, $ )

*( S, "<ass>" , <R3> ) = ( S, $, $ )

*( S, "</boolean>" , <R4> ) = ( S, $, $ )

*( S, "</char>" , <R5> ) = ( S, $, $ )

*( S, -|, <R6> ) = ( S, $, $ )

Для каждого bV_твх, не стоящего на первом месте в правой части правил транслирующей грамматики, строим функции вида:f( S, b, b) = ( S, $, $).

( S, "," , "," ) = ( S, $, $ )

( S, "</arr>" , "</arr>" ) = ( S, $, $ )

( S, "</earr>" , "</earr>" ) = ( S, $, $ )

( S, "</boolean>" , "</boolean>" ) = ( S, $, $ )

( S, "</char>" , "</char>" ) = ( S, $, $ )

( S, "</ass>" , "</ass>" ) = ( S, $, $ )

( S, "</and>" , "</and>" ) = ( S, $, $ )

( S, "</or>" , "</or>" ) = ( S, $, $ )

( S, "</not>" , "</not>" ) = ( S, $, $ )

Для каждого wV_твых, записываемого в магазин, строим функции вида:

f*( S, $, w) = ( S, $, w).

*( S, $, #bool#) = (S, $, #bool# )

*( S, $, #char#) = (S, $, #char# )

*( S, $, #a#) = (S, $, #a# )

*( S, $, #b#) = (S, $, #b# )

*( S, $, #c#) = (S, $, #c# )

*( S, $, #d#) = (S, $, #d# )

*( S, $, #e#) = (S, $, #e# )

*( S, $, #0#) = (S, $, #0# )

*( S, $, #1#) = (S, $, #1# )

*( S, $, #2#) = (S, $, #2# )

*( S, $, #3#) = (S, $, #3# )

*( S, $, #4#) = (S, $, #4# )

*( S, $, #5#) = (S, $, #5# )

*( S, $, #6#) = (S, $, #6# )

*( S, $, #7#) = (S, $, #7# )

*( S, $, #8#) = (S, $, #8# )

*( S, $, #9#) = (S, $, #9# )

*( S, $, # #) = (S, $, # # )

*( S, $, #RM#) = (S, $, #RM# )

*( S, $, #EM#) = (S, $, #EM# )

*( S, $, #=#) = (S, $, #=# )

*( S, $, #&#) = (S, $, #&# )

*( S, $, #V#) = (S, $, #V# )

*( S, $, #!#) = (S, $, #!# )

*( S, $, #'true'#) = (S, $, #'true'# )

*( S, $, #'false'#) = (S, $, #'false'# )

*( S, $, #'a'#) = (S, $, #'a'# )

*( S, $, #'b'#) = (S, $, #'b'# )

*( S, $, #'c'#) = (S, $, #'c'# )

*( S, $, #'d'#) = (S, $, #'d'# )

*( S, $, #'e'#) = (S, $, #'e'# )

Строим функцию перехода в заключительное состояние:

( S, -|, [] ) = (S, $, $ )

Пример работы магазинного преобразователя:

Подадим на вход цепочку:

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

На выходе магазинного преобразователя получим цепочку:

b1 bool b1 ’false’ ! =

ТАКТ 0

состояние S

входная цепочка "<boolean>" b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"

магазин []

выходная цепочка

функция перехода *(S,"<BOOLEAN>",)=(S,<CODE># #<VARS>,$)

ТАКТ 1

состояние S

входная цепочка "<boolean>" b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"

магазин <VARS># #<CODE>[]

выходная цепочка

функция перехода (S,"<BOOLEAN>",<VARS>)=(S,<R3>"</BOOLEAN>"<NAMESBOOL>,$)

ТАКТ 2

состояние S

входная цепочка b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин <NAMESBOOL>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода *(S,B,<NAMESBOOL>)=(S,<R4>#BOOL## #<ID>,$)

ТАКТ 3

состояние S

входная цепочка b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин <ID># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода *(S,B,<ID>)=(S,<R1><BUKVA>,$)

ТАКТ 4

состояние S

входная цепочка b1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин <BUKVA><R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода (S,B,<BUKVA>)=(S,#B#,$)

ТАКТ 5

состояние S

входная цепочка 1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин #B#<R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка

функция перехода *(S,$,#B#)=(S,$,#B#)

ТАКТ 6

состояние S

входная цепочка 1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин <R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка B

функция перехода *(S,1,<R1>)=(S,<R1><ZIFRA>,$)

ТАКТ 7

состояние S

входная цепочка 1 "</boolean>""<ass>" b1, "<not>" "'false'" "</not>" "</ass>"-|

магазин <ZIFRA><R1># ##BOOL#<R4>"</BOOLEAN>"<R3># #<CODE>[]

выходная цепочка B

функция перехода (S,1,<ZIFRA>)=(S,#1#,$)

ТАКТ 8

состояние S