View
35
Download
0
Category
Preview:
DESCRIPTION
Una introducción a los algoritmos del Parsing. Pregunta inicial …. ¿Cómo se puede determinar si un código escrito en un lenguaje de programación tiene sintaxis correcta?. Leftmost Derivations. - PowerPoint PPT Presentation
Citation preview
Una Una introducción a introducción a los algoritmos los algoritmos
del Parsingdel Parsing
Pregunta inicialPregunta inicial……
¿Cómo se puede ¿Cómo se puede determinar si un código determinar si un código
escrito en un lenguaje de escrito en un lenguaje de programación tiene programación tiene sintaxis correcta?sintaxis correcta?
Leftmost DerivationsLeftmost Derivations
Una Una derivación a izquierdaderivación a izquierda de una cadena de una cadena sólo permite resolver en cada paso la sólo permite resolver en cada paso la variable más a la izquierdavariable más a la izquierda
aaBA aaBA => => aaBaaaBa NO hace parte de una NO hace parte de una derivación a izquiereda.derivación a izquiereda.
Si Si ww está en está en L(G)L(G) entonces entonces ww admite una admite una derivación a izquierda (Teorema 4.1.1).derivación a izquierda (Teorema 4.1.1).
AmbiguedadAmbiguedad
Una gramática Una gramática GG es es ambiguaambigua si existe si existe ww en en L(G)L(G) que admite dos derivaciones a que admite dos derivaciones a izquierda.izquierda.
s aS | Sa | a Es ambigua porque aa admite dos derivaciones a izquierda:
S => aS =>aa S => Sa =>aa
Un Lenguaje es inherentemente ambiguo, si todas las gramáticas que lo generan son ambiguas.
Ejemplo 4.1.2Ejemplo 4.1.2s bS | Sb | a Genera el lenguaje b*ab*. Es ambigua porque bab
admite dos derivaciones a izquierda:
S => bS =>bSb=>bab S => Sb =>bSb=>bab
b*ab* se puede generar por las gramáticas no ambiguas:
S bS | aA
A bA |
S bS | A
A Ab | a
Existe una correspondencia biyectiva entre los árboles de derivación y las derivaciones a izquierda (a derecha).
Grafo de una Grafo de una gramática.gramática.
S aS | bB |
B aB | bS | bC
C aC |
S
aS
bB
aaSabB a baB
bbSbbC
aaaS
aabB
aa
abaBabbS
abbCbaaB
babS babCbbaS
bbbBbb bbaC
bb
Recorrido transversal descendenteRecorrido transversal descendente
EJEMPLOEJEMPLO
Dada la gramática:Dada la gramática:
AE: V = AE: V = {S, A, T}{S, A, T}
ΣΣ = = {b, +, (, )}{b, +, (, )}
P: 1. S → AP: 1. S → A
2. A → T2. A → T
3. A → A + T3. A → A + T
4. T → b4. T → b
5. T → (A)5. T → (A)
analizar la cadena (b + b)analizar la cadena (b + b)
(b)(b)
b (T)b (T) ((A)) ((A)) (b+T) ( b+b) (b+T) ( b+b)
TT (T+T)(T+T) ((A)+T) ((A)+T)
(A) (A) (A+T)(A+T)(A+T+T)(A+T+T) (T+T+T)(T+T+T)
S A S A (A+T+T+T) (A+T+T+T) b+T b+T
(b)+T(b)+TT+TT+T (A)+T(A)+T (T)+T(T)+T ((A))+T((A))+T
A+T A+T (A+T)+T (A+T)+T (T+T)+T(T+T)+T(A+T+T)+T(A+T+T)+T
b+T+Tb+T+TA+T+TA+T+T T+T+TT+T+T (A)+T+T(A)+T+T (T)+T+T(T)+T+T
(A+T)+T+T(A+T)+T+T
b+T+T+Tb+T+T+TA+T+T+TA+T+T+T T+T+T+TT+T+T+T (A)+T+T+T(A)+T+T+T
11 A+T+T+T+TA+T+T+T+T T+T+T+T+TT+T+T+T+TA+T+T+T+T+TA+T+T+T+T+T
(A),T+T,A+T+T T+T,A+T+T,(T) T+T,A+T+T,(T),(A+T)
Breadth-First Top-down Parsing AlgorithmBreadth-First Top-down Parsing Algorithminput: input: context-free grammar G = (V, context-free grammar G = (V, Σ, P, Σ, P, SS))
string string pp Σ*Σ*
queue queue QQ
1.1. initialize T with root initialize T with root SS
INSERTINSERT((SS, , QQ))
2. 2. repeatrepeat
2.1. 2.1. qq ≔≔ REMOVEREMOVE((QQ))
2.2. 2.2. ii ≔ ≔ 00
2.3. 2.3. donedone ≔≔ false false
Let Let qq = = uuAAvv where A is the leftmost variable in where A is the leftmost variable in qq..
2.4. 2.4. repeatrepeat
2.4.1. 2.4.1. ifif there is no A rule numbered greater than there is no A rule numbered greater than ii thenthen done ≔ done ≔ truetrue
2.4.2. 2.4.2. ifif not done not done thenthen
Let A → Let A → ww be the first A rule with number grater than i. Let be the first A rule with number grater than i. Let jj
be the number of this rule.be the number of this rule.
2.4.2.1. 2.4.2.1. ifif uwvuwv ∉∉ ΣΣ* and the terminal prefix or * and the terminal prefix or uwvuwv matches a matches a
prefix of prefix of pp thenthen
2.4.2.1.1. 2.4.2.1.1. INSERTINSERT((uwvuwv, , QQ))
2.4.2.1.2. 2.4.2.1.2. Add node Add node uwvuwv to T. Set a pointer from to T. Set a pointer from
uwvuwv to to qq..
end ifend if
end ifend if
2.4.3 2.4.3 ii ≔ ≔ jj
untiluntil done done oror p = uwvp = uwv
untiluntil EMPTY( EMPTY( QQ) ) oror p = uwvp = uwv
3. 3. ifif p p = = uwvuwv thenthen accept accept elseelse reject reject
Recorrido descendente profundoRecorrido descendente profundo
AE: AE: V = V = {S, A, T}{S, A, T} ΣΣ = = {b, +, (, )}{b, +, (, )} P:P: 1. 1. S → A S → A 2. 2. A → T A → T 3. 3. A → A + TA → A + T 4. 4. T → bT → b 5. 5. T → (A)T → (A)p= (b + b)p= (b + b)
S
A
[S,1]
T
[A,2]
b
[T,4]
(A)
[T,5](T)[(A),2]
[(T),4]
(b) ((A))
[(T),5]
(A+T)
[(A),3]
[(A+T),2](T+T)
(b+T)[(T+T),4]
(b+b)
[(b+T),4]
(b+b)
Depth-First Top-down AlgorithmDepth-First Top-down Algorithminput: input: context-free grammar G = (V, context-free grammar G = (V, Σ, P, Σ, P, SS)) string string pp Σ*Σ*
stack stack SS1.1. PUSHPUSH(([S, 0], [S, 0], SS))2.2. repearepeatt 2.12.1 [[qq, , ii] = ] = POPPOP((SS))
2.22.2 dead-end = dead-end = falsefalse2.32.3 repeatrepeat Let Let qq = = uuAAv v where A is the leftmost variable in where A is the leftmost variable in qq..
2.3.1 2.3.1 ifif u u is not a prefix of p is not a prefix of p thenthen dead-end = dead-end = truetrue2.3.2 2.3.2 ifif there are no A rules numbered greater there are no A rules numbered greater ii thenthen dead-end = dead-end = truetrue2.3.3 2.3.3 if notif not dead-end dead-end thenthen
Let A → Let A → ww be the first A rule with number greater than be the first A rule with number greater than i i..Let Let jj be the number of this rule. be the number of this rule.2.3.3.1 2.3.3.1 PUSHPUSH(([[qq, , jj], ], SS))2.3.3.22.3.3.2 q = q = uwvuwv2.3.3.32.3.3.3 ii = 0 = 0
end ifend ifuntiluntil dead-end or q dead-end or q ΣΣ**
untiluntil qq = = pp or or EMPTYEMPTY((SS))3.3. ifif qq = = pp thenthen accept accept elseelse reject reject
AE: AE: V = V = {S, A, T}{S, A, T} ΣΣ = = {b, +, (, )}{b, +, (, )} P:P: 1. 1. S → A S → A 2. 2. A → T A → T 3. 3. A → A + TA → A + T 4. 4. T → bT → b 5. 5. T → (A)T → (A)p= (b )+ bp= (b )+ b
S
A
[S,1]
T
[A,2]b
[T,4]
(A)
[T,5]
(T)
[(A),2]
[(T),4]
(b) ((A))
[(T),5](A+T)[(A),3]
[(A+T),2]
(T+T)
(b+T)
[(T+T),4]
((A)+T)
[(T+T),5]
[(A+T),3]
(A+T+T)
[(A+T+T),2]
Algoritmos AscendentesAlgoritmos Ascendentes
Reducción: Dado Reducción: Dado ww encontrar las encontrar las w’w’ tales tales que que w’=>ww’=>w. En este caso . En este caso w’w’ es una es una reducciónreducción de de ww..
Pattern Matching Scheme: Se descompone Pattern Matching Scheme: Se descompone ww en en w=uvw=uv, los sufijos de , los sufijos de uu se comparan se comparan con los lados derechos de las reglas.con los lados derechos de las reglas.
Un “matching” se obtiene cuando se Un “matching” se obtiene cuando se encuentra encuentra u=uu=u11qq y una regla y una regla AAqq entonces entonces
ww se reduce a se reduce a uu11AvAv..
Reducción de Reducción de (A+T)(A+T)
u v Regla Reducción
(A+T)
( A+T)
( A +T) S A (S+T)
( A+ T)
( A+T ) A A+T (A)
(A+T ) A T (A+A)
( A+T)
Algoritmo ascendente transversalAlgoritmo ascendente transversalAE: AE: V = V = {S, A, T}{S, A, T} ΣΣ = = {b, +, (, )}{b, +, (, )} P:P: 1. 1. S → A S → A 2. 2. A → T A → T 3. 3. A → A + TA → A + T 4. 4. T → bT → b 5. 5. T → (A)T → (A)p= (b + b)p= (b + b)
(b+b)
(b+T) (T+b)
(A+b)(T+T)(b+A)
(A+b), (T+T), (b+A)
(S+b)
(T+T), (b+A), (S+b)
(A+T)
(T+T), (b+A), (S+b), (A+T)
(T+A)
(b+A), (S+b), (A+T), (T+A)
(b+S)
(S+b), (A+T), (T+A), (b+S) (A+T), (T+A), (b+S), (S+T)
(A+A)
(T+A), (b+S), (S+T), (A+A),(A)
(A)(T+S)
(b+S), (S+T), (A+A),(A), (T+S)
(S+T), (A+A),(A), (T+S)
(A+S)
(A+A),(A), (T+S), (S+A)
(S+T)
(S+A)
(A), (T+S), (S+A),(A+S)
(S)T
(T+S), (S+A), (A+S), (S), T
(S+A), (A+S), (S), T
(S+S)
(A+S), (S), T, (S+S)
T, (S+S)
A
(S+S), A
A
S
S
Breadth-First Bottom-up ParserBreadth-First Bottom-up ParserInput: Input: context-free grammar G = (V, context-free grammar G = (V, Σ, P, Σ, P, SS))
string string pp Σ*Σ*queue queue QQ
1.1. Initialize T with root Initialize T with root ppINSERTINSERT((pp,,QQ))
2.2. repeatrepeat q q ≔ ≔ REMOVEREMOVE((QQ))
2.1. 2.1. forfor each rule each rule AA → → ww in P in P dodo
2.1.1.2.1.1. ifif q = q = uwvuwv with with vv Σ* Σ* thenthen 2.1.1.1 2.1.1.1 INSERTINSERT((uAvuAv, , QQ))2.1.1.22.1.1.2 Add node Add node uAvuAv to T. Set a pointer to T. Set a pointer
from from uAvuAv to to qq. . end ifend if
end forend foruntiluntil qq = = SS oror EMPTYEMPTY((QQ))
3.3. IfIf qq = = SS thenthen accept accept elseelse reject reject
(T+b)
AE: AE: V = V = {S, A, T}{S, A, T} ΣΣ = = {b, +, (, )}{b, +, (, )} P:P: 1. 1. S → A S → A 2. 2. A → TA → T 3. 3. A → A + TA → A + T 4. T → b4. T → b 5. 5. T → (A)T → (A)
(A+b) (T+T)
[ (T , 2 , +b) ] [ (T+b , 4 , ) ]
(T+A)
(A+T)
[ (A+b , 2 ,) ] (T+A)
(A+b)
(A+b)
Depth-Bottom-up Parsing AlgorithmDepth-Bottom-up Parsing Algorithminput: input: context-free grammar G = (V, context-free grammar G = (V, Σ, P, Σ, P, SS) with nonrecursive start symbol) with nonrecursive start symbol
string string pp Σ*Σ*stack stack SS
1.1. PUSHPUSH([([λλ, 0, , 0, pp], ], SS))2.2. repeatrepeat 2.1 2.1 [[uu, , ii, , vv] ] ≔ ≔ POPPOP((SS)) 2.2 2.2 dead-end dead-end ≔ ≔ falsefalse
2.3 2.3 repeatrepeat Find the first Find the first jj > > ii with rule number with rule number jj that satisfies that satisfies ii) ) AA → → ww with with uu = = qwqw and and AA ≠ ≠ SS oror
iiii) ) SS → → ww with with uu = = ww and and vv = = λλ 2.3.1. 2.3.1. ifif there is such a there is such a jj then then 2.3.1.1. 2.3.1.1. PUSHPUSH ( ([[uu, , jj, , vv], ], SS))
2.3.1.2. 2.3.1.2. uu ≔ ≔ qAqA 2.3.1.3. 2.3.1.3. ii ≔ ≔ 00 end ifend if 2.3.2 2.3.2 ifif there is no such there is no such jj and and v v ≠ ≠ λλ thenthen 2.3.2.1. 2.3.2.1. shiftshift((uu, , vv)) 2.3.2.2. 2.3.2.2. ii ≔ ≔ 00 end ifend if 2.3.3 2.3.3 ifif there is no such there is no such jj and and vv = = λλ thenthen dead-end dead-end ≔ ≔ truetrue untiluntil ( (uu = = SS) ) oror dead-end dead-end untiluntil ( (uu = = SS) ) oror EMPTYEMPTY((SS))3. 3. ifif EMPTY(SEMPTY(S) ) thenthen reject reject elseelse accept accept
AE: AE: V = V = {S, A, T}{S, A, T} ΣΣ = = {b, +, (, )}{b, +, (, )} P:P: 1. S → A1. S → A 2. A → T2. A → T 3. A → A + T3. A → A + T 4. T → b4. T → b 5. T → (A)5. T → (A)
u i v
0 (b+b)
[ , 0 , (b+b) ]
( 0 b+b)
(b 0 +b)
[ (b, 4 , +b) ]
(T 0 +b)
[ (T, 2 , +b) ]
(A 0 +b)
(A+ 0 b)
(A+b 0 )
[ (A+b, 4 , ) ]
(A+T 0 )
[ (A+T, 2 , ) ]
(A+A 0 )
(A+A) 0 (A+T 2 )[ (A+T, 3 , ) ] (A 0 )
(A ) 0
[ (A), 5 , ]
T 0
[ T, 2 , ]
A 0
[ A, 2 , ]
S 0
Notas BibliográficasNotas Bibliográficas
Ambigüedad: Floyd[1962], Cantor[1962], Ambigüedad: Floyd[1962], Cantor[1962], Chomsky and Schutzenberger [1963].Chomsky and Schutzenberger [1963].
Lenguajes Inherentemente ambiguos: Lenguajes Inherentemente ambiguos: Harrison[1978], Ginsburg and Ullian[1966].Harrison[1978], Ginsburg and Ullian[1966].
Depth-first: Dennig, Dennis and Depth-first: Dennig, Dennis and Qualitz[1978].Qualitz[1978].
Referencia Clásica: Knuth: “Referencia Clásica: Knuth: “The Art of The Art of Computer programing: Vol I Fundamental Computer programing: Vol I Fundamental AlgorithmsAlgorithms” ”
Recommended