Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 28 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

28
T
TF
*
x
F
E
)(
+
TE
T
F
F
x
y
E
Рис. 4.1. Дерево разбора.
Проблему разбора можно свести к
1) нахождению левостороннего разбора;
2) нахождению правостороннего разбора;
3) построению синтаксического дерева.
Неоднозначные грамматики
. В большинстве случаев левосторонний
и правосторонний разборы и синтаксическое дерево являются уникальными.
Однако для грамматики с порождающими правилами:
S
→
S+S | x
предложение x + x + x имеет два синтаксических дерева (рис. 4.2) и два
левосторонних (и правосторонних) разбора:
S
SS
SS
+
+
xx
x
x
xx
S
S
S
SS
+
+
Рис. 4.2. Варианты разбора. 
                                                                         28



                                             E

                                             T

                                     T       *       F

                                     F               x

                             (       E       )

                             E       +       T

                             T               F

                             F               y

                             x

                         Рис. 4.1. Дерево разбора.


     Проблему разбора можно свести к
        1) нахождению левостороннего разбора;
        2) нахождению правостороннего разбора;
        3) построению синтаксического дерева.
     Неоднозначные грамматики. В большинстве случаев левосторонний
и правосторонний разборы и синтаксическое дерево являются уникальными.
Однако для грамматики с порождающими правилами:
     S → S+S | x
     предложение x + x + x имеет два синтаксических дерева (рис. 4.2) и два
левосторонних (и правосторонних) разбора:


                                 S                       S

                        S        +       S       S       +   S

                   S    +        S       x       x       S   +   S

                   x             x                       x       x


                            Рис. 4.2. Варианты разбора.

Страницы