Python

[palamo1]

Помогите студенту с грамматикой простого предшествования:(
Пожалйста!
Лабор. задание 3

Грамматики простого и слабого предшествования


По каждой КС-грамматике G можно построить таблицу

предшествования T (точнее говоря, T(G)). Строки и столбцы таблицы

однозначно поименованы основными и вспомогательными символами грамматики

и дополнительным символом #.

  В клетки T(x,y) таблицы помещаются символы <,=,> по следующим

правилам (в которых u и v могут быть произвольными строками):

  1) T(x,y) содержит <, если G содержит правило вида A->uxBv такое,

что существует непустой вывод строки, начинающейся с y, из символа B.

  2) T(x,y) содержит >, если y - основной символ, и G содержит правило

вида A->uBZv такое, что существуют непустой вывод строки, кончающейся

на x, из символа B и (возможно, пустой) вывод строки, начинающейся

с y, из символа Z (когда упомянутый последним вывод пуст, Z  совпадает

с y).

  3) T(x,y) содержит =, если G содержит правило вида A->uxyv.

  4) T(#,y) содержит <, если в G из аксиомы можно вывести

строку, начинающуюся с y.

  5) T(x,#) содержит >, если в G из аксиомы можно вывести

строку, кончающуюся на x.


   Если T(x,y) содержит <, > или =, будем употреблять также

обозначения x<y, x>y, x=y, соответственно (заметим, что одно-

временно может быть x<y, x>y и x=y).


    G называется грамматикой простого предшествования, если

каждое из множеств T(x,y) содержит не более одного элемента.

    G называется грамматикой слабого предшествования, если

1) каждое из множеств T(x,y) одновременно ссимволом > не может

содержать ни символа <, ни символа =, 2) если G содержит два

правила A->uXv и B->v, то не может быть ни X<B, ни X=B.


Следующая грамматика для арифметических выражений типа a+a*(a*a+a)

является обратимой грамматикой слабого (но не простого) предшествования.


E->E+T | T

T->T*F | F

F->(E) | a


Ниже приводится таблица предшествования для этой грамматики


  | E  T  F  a  (  )  +  *  #

__|___________________________

E |                =  =     

T |                >  >  =  >

F |                >  >  >  >

a |                >  >  >  >

) |                >  >  >  >

( |<=  <  <  <  <

+ |    <= <  <  <

* |       =  <  <

# | <  <  <  <  <


Алгоритм анализа.
Ниже будем считать, что G - обратимая (т.е. не содержит

разных правил с одинаковой правой частью) и приведенная

(т.е. не содержит выводов вида A->B->...->A, и удовлетворяет

некоторым другим простым условиям, которые обычно выполняются

для естественным образом построенных грамматик).


Пусть s - входная строка, дополненная в конце символом #,

и m - вспомогательная строка (стек), вначале равная #.
На каждом шаге работы имеется указатель на некоторый символ строки

s (в начале работы указывается первый символ s) и указатель

на последний символ стека m. 


Алгоритм состоит из этапов переноса и свертки.

Пусть x - последний символ стека m, y - очередной символ во

входной строке s.

1) Если x<y или x=y, то y переносится в m, и указатель на

s переносится на следующий символ.

2) Если x>y, то в хвосте m производится свертка (т.е. замена

правой части некоторого правила на его левую часть), если это

возможно. Для грамматик простого предшествования такое правило

(если оно есть) определяется однозначно. Для грамматик слабого

предшествования это может быть не так: в этом случае надо

заменять самую длинную правую часть. Если такого правила нельзя

найти, то s нельзя вывести в G;

3) Если T(x,y) пусто, то s нельзя вывести в G (кроме случая

x=E,y=#, в этом случае надо выйти из цикла и проверить  стек

на равенство с #E как ниже).


Если таким образом удается обработать всю строку s и в конце

работы m равен #E, где E - аксиома грамматики G, то делается

вывод, что s можно вывести в G, а в противном случае -

s не выводится в G.