Здавалка
Главная | Обратная связь

Пример разбора цепочки, порождаемой заданной грамматикой предшествования

⇐ ПредыдущаяСтр 12 из 12

Цепочка: (())()

(┴,(())(),ε) ->

(┴(,())(),ε) ->

(┴((,))(),ε) ->

(┴((),)(),ε) ->

(┴(A,)(),4) ->

(┴(S,)(),42) ->

(┴(S),(),42) ->

(┴A,(),423) ->

(┴S,(),4232) ->

(┴S(,),4232) ->

(┴S(),ε,4232) ->

(┴SA,ε,42324) ->

(┴S,ε,423241) ->

ДОПУСК


 

Построить анализатор типа "перенос-свертка" и промоделировать его работу для следующих грамматик слабого предшествования G = < T, N, S, R >

 

7.2.4. T = { i, or, and, not, (, ) }, N = { S, T, P ), R = { S ® S or T, S ® T, T ® T and P, T ® P, P ® i, P ® ( S ), P ® not P };

 

1. Отношение (=) определяется непосредственно из правил грамматики

  S T P I Or And Not ( )
S         =       =
T           =      
P                  
I                  
or   =              
and     =            
not     =            
( =                
)                  
┴                  

 

2. Определим отношения FIRSTN и LASTN

FIRSTN S T P I Or And Not ( )
S              
T              
P            
LASTN                  
S                
T                
P            

 

Построим транзитивные замыкания данных отношений

FIRSTN+ S T P I Or And Not ( )
S      
T        
P            
LASTN+                  
S          
T            
P            

 


 

3. Представим отношения в виде булевых матриц, строки и столбцы которых обозначены символами грамматики в порядке S T P i or and not ( )

 

Тогда матрицу отношения (<•) получим из соотношения (<•) = (=)(FIRSTN+)

 

 

 

=

 

 

Т.е. отношение (<•) определяется следующим образом

 

  S T P I Or And Not ( )
|S                  
T                  
P                  
I                  
Or   <• <• <•     <• <•  
and       <•     <• <•  
Not       <•     <• <•  
( <• <• <• <•     <• <•  
)                  
┴                  

 

матрицу отношения (•>) получим из соотношения (•>) =((LASTN+)T) (=)(E+FIRSTN+)

 

 

(LASTN+)=

 


 

(LASTN+)T=

 

 

((LASTN+)-1)(=) =

 

 

(E+FIRTSN+) =

 

 

((LASTN+)-1)(=) (E+FIRTSN+) =

 

 


 

Значит матрица отношений предшествования для данной грамматики выглядит следующим образом

  S T P I Or And Not ( ) ε
|S         =       = •>
T           =       •>
P                   •>
i                   •>
or   <•= <• <•     <• <•    
and     = <•     <• <•    
not     = <•     <• <•    
( <•= <• <• <•     <• <•    
)                   •>
┴ <• <• <• <•     <• <•    

 

 

Используя таблицу отношений предшествования построим функцию переноса

 

  S T P i or and not ( ) ε
|S         П       П С
T         С П     С С
P         С С     С С
i         С С     С С
or   П П П     П П    
and     П П     П П    
not     П П     П П    
( П П П П     П П    
)         С С     С С
┴ П П П П     П П    
┴S                   Д

 

И функцию свертки

 

X β g(α)
┴ S or T
┴ T
( S or T
( T
┴ T and P
┴ P
( T and P
( P
or T and P
or P
┴ i
┴ (S)
┴ Not P
( i
( (S)
( Not P
or i
or (S)
or Not P
and i
and (S)
and Not P
not i
not (S)
not Not P

 

 

Контрольный пример - разбор цепочки (not i ) and i or not i, принадлежащей языку

 

(┴, (not i ) and i or not I,ε)

(┴ ( , not i ) and i or not I, ε)

(┴ (not, i ) and i or not I, ε)

(┴ (not i,) and i or not I, ε)

(┴ (not P , ) and i or not I,5)

(┴ (P , ) and i or not I,57)

(┴ (T ,) and i or not I,574)

(┴ (S ,) and i or not I,5742)

(┴ (S) , and i or not I,5742)

(┴P, and i or not I,57426)

(┴T , and i or not I,574264)

(┴Tand, i or not I,574264)

(┴Tand I, or not I,574264)

(┴Tand P , or not I,5742645)

(┴T , or not I,57426453)

(┴S , or not i,574264532)

(┴Sor , not I,574264532)

(┴Sor not , I,574264532)

(┴Sor not I , ε,574264532)

(┴Sor not P , ε,5742645325)

(┴Sor P, ε,57426453257)

(┴Sor T , ε,574264532574)

(┴S, ε, 5742645325741)

ДОПУСК


 

Построить анализатор типа "перенос-свертка" и промоделировать его работу для следующих грамматик слабого предшествования G = < T, N, S, R >

 

7.2.4. T = { i, or, and, not, (, ) }, N = { S, T, P ), R = { S ® S or T, S ® T, T ® T and P, T ® P, P ® i, P ® ( S ), P ® not P };

 

1. Отношение (=) определяется непосредственно из правил грамматики

  S T P I Or And Not ( )
S         =       =
T           =      
P                  
I                  
or   =              
and     =            
not     =            
( =                
)                  
┴                  

 

2. Определим отношения FIRSTN и LASTN

FIRSTN S T P I Or And Not ( )
S              
T              
P            
LASTN                  
S                
T                
P            

 

Построим транзитивные замыкания данных отношений

FIRSTN+ S T P I Or And Not ( )
S      
T        
P            
LASTN+                  
S          
T            
P            

 


 

3. Представим отношения в виде булевых матриц, строки и столбцы которых обозначены символами грамматики в порядке S T P i or and not ( )

 

 

Тогда матрицу отношения (<•) получим из соотношения (<•) = (=)(FIRSTN+)

 

 

 

 

=

 

 

Т.е. отношение (<•) определяется следующим образом

 

  S T P I Or And Not ( )
|S                  
T                  
P                  
I                  
Or   <• <• <•     <• <•  
and       <•     <• <•  
Not       <•     <• <•  
( <• <• <• <•     <• <•  
)                  
┴                  

 

 

матрицу отношения (•>) получим из соотношения (•>) =((LASTN+)T) (=)(E+FIRSTN+)

 

 

(LASTN+)=

 

(LASTN+)T=

 

 

((LASTN+)-1)(=) =

 

 

(E+FIRTSN+) =

 

 

((LASTN+)-1)(=) (E+FIRTSN+) =

 

 

Значит матрица отношений предшествования для данной грамматики выглядит следующим образом

  S T P I Or And Not ( ) ε
|S         =       = •>
T           =       •>
P                   •>
i                   •>
or   <•= <• <•     <• <•    
and     = <•     <• <•    
not     = <•     <• <•    
( <•= <• <• <•     <• <•    
)                   •>
┴ <• <• <• <•     <• <•    

 

 

Используя таблицу отношений предшествования построим функцию переноса

 

  S T P i or and not ( ) ε
|S         П       П С
T         С П     С С
P         С С     С С
i         С С     С С
or   П П П     П П    
and     П П     П П    
not     П П     П П    
( П П П П     П П    
)         С С     С С
┴ П П П П     П П    
┴S                   Д

 

 


 

И функцию свертки

 

X β g(α)
┴ S or T
┴ T
( S or T
( T
┴ T and P
┴ P
( T and P
( P
or T and P
or P
┴ i
┴ (S)
┴ Not P
( i
( (S)
( Not P
or i
or (S)
or Not P
and i
and (S)
and Not P
not i
not (S)
not Not P

 

 


 

Контрольный пример - разбор цепочки (not i ) and i or not i, принадлежащей языку

 

(┴, (not i ) and i or not I,ε)

(┴ ( , not i ) and i or not I, ε)

(┴ (not, i ) and i or not I, ε)

(┴ (not i,) and i or not I, ε)

(┴ (not P , ) and i or not I,5)

(┴ (P , ) and i or not I,57)

(┴ (T ,) and i or not I,574)

(┴ (S ,) and i or not I,5742)

(┴ (S) , and i or not I,5742)

(┴P, and i or not I,57426)

(┴T , and i or not I,574264)

(┴Tand, i or not I,574264)

(┴Tand I, or not I,574264)

(┴Tand P , or not I,5742645)

(┴T , or not I,57426453)

(┴S , or not i,574264532)

(┴Sor , not I,574264532)

(┴Sor not , I,574264532)

(┴Sor not I , ε,574264532)

(┴Sor not P , ε,5742645325)

(┴Sor P, ε,57426453257)

(┴Sor T , ε,574264532574)

(┴S, ε, 5742645325741)

ДОПУСК

Построить анализатор типа "перенос-свертка" и промоделировать его работу для следующих грамматик операторного предшествования G=<T,N,S,R>

⇐ Предыдущая3456789101112






©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.