LL parser

Inom datavetenskap är en LL-parser (vänster-till-höger, avledning längst till vänster ) en top-down-parser för ett begränsat sammanhangsfritt språk . Den analyserar inmatningen från vänster till höger och utför en härledning till vänster av meningen.

En LL-parser kallas en LL( k )-parser om den använder k- tecken av lookahead när den analyserar en mening. En grammatik kallas en LL( k )-grammatik om en LL( k )-parser kan konstrueras från den. Ett formellt språk kallas ett LL( k )-språk om det har en LL( k )-grammatik. Uppsättningen LL( k )-språk är korrekt inkluderad i LL( k +1)-språken, för varje k ≥ 0. En följd av detta är att inte alla sammanhangsfria språk kan kännas igen av en LL( k )-tolkare.

En LL-parser kallas LL-regular (LLR) om den analyserar ett LL-regular-språk . ^{[ förtydligande behövs ]} Klassen LLR-grammatik innehåller varje LL(k)-grammatik för varje k. För varje LLR-grammatik finns det en LLR-parser som analyserar grammatiken i linjär tid. ^{[ citat behövs ]}

Två nomenklativa outlier-parsertyper är LL(*) och LL(finite). En parser kallas LL(*)/LL(finite) om den använder LL(*)/LL(finite) analysstrategin. LL(*)- och LL(finita)-parsrar är funktionellt mer lik PEG- parsrar. En LL(finite)-parser kan analysera en godtycklig LL(k)-grammatik optimalt i mängden lookahead och lookahead-jämförelser. Klassen av grammatiker som kan analyseras med LL(*)-strategin omfattar vissa kontextkänsliga språk på grund av användningen av syntaktiska och semantiska predikat och har inte identifierats. Det har föreslagits att LL(*)-tolkare är bättre att betrakta som TDPL parsers. Mot den populära missuppfattningen är LL(*)-parsrar inte LLR i allmänhet och garanteras av konstruktionen att prestera sämre i genomsnitt (superlinjär mot linjär tid) och mycket sämre i värsta fall (exponentiell mot linjär tid).

LL-grammatik, särskilt LL(1)-grammatik, är av stort praktiskt intresse, eftersom tolkar för dessa grammatiker är lätta att konstruera, och många datorspråk är designade för att vara LL(1) av denna anledning. LL-parsers kan vara tabellbaserade, ^{[ citat behövs ]} dvs liknar LR-parsers , men LL-grammatiker kan också analyseras av rekursiva descent-parsers . Enligt Waite och Goos (1984) introducerades LL( k )-grammatik av Stearns och Lewis (1969).

Översikt

För en given kontextfri grammatik försöker analysatorn hitta härledningen längst till vänster . Med tanke på ett exempel på grammatik $G$ :

$S\to E$
$E\to (E+E)$
$E\to i$

härledningen längst till vänster för $w=((i+i)+i)$ är:

S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ ( E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+ E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)

Generellt sett finns det flera möjligheter när man väljer en regel för att expandera den icke-terminal längst till vänster. I steg 2 i föregående exempel måste analysatorn välja om regel 2 eller regel 3 ska tillämpas:

S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?

För att vara effektiv måste parsern kunna göra detta val deterministiskt när det är möjligt, utan att backa. För vissa grammatiker kan den göra detta genom att kika på den olästa inmatningen (utan att läsa). I vårt exempel, om analysatorn vet att nästa olästa symbol är $($ , är den enda korrekta regeln som kan användas 2.

I allmänhet kan en ${\displaystyle LL(k)}-$ parser se framåt på $k$ -symboler. Men givet en grammatik är problemet med att avgöra om det finns en ${\displaystyle LL(k)}-$ parser för vissa $k$ som känner igen det oavgörbart. För varje $k$ finns det ett språk som inte kan kännas igen av en ${\displaystyle LL(k)}-$ tolkare, men kan vara av en $LL(k+1)$ .

Vi kan använda ovanstående analys för att ge följande formella definition:

Låt $G$ vara en kontextfri grammatik och $k\geq 1$ . Vi säger att $G$ är $LL(k)$ , om och endast om för två avledningar längst till vänster:

$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \ \Rightarrow \ \cdots \ \Rightarrow \ wu$
$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \ \Rightarrow \ \cdots \ \Rightarrow \ wv$

följande villkor gäller: prefixet för strängen $u$ av längden $k$ är lika med prefixet för strängen $v$ av längden $k$ innebär ${\ displaystyle \beta \ =\ \gamma }$ .

I denna definition är $S$ startsymbolen och $A$ vilken som helst icke-terminal. Den redan härledda ingången $w$ och ännu olästa $u$ och $v$ är strängar av terminaler. De grekiska bokstäverna $\alpha$ , $\beta$ och $\gamma$ representerar vilken sträng som helst av både terminaler och icke-terminaler (eventuellt tomma). Prefixets längd motsvarar storleken på lookahead-bufferten, och definitionen säger att denna buffert räcker för att skilja mellan två avledningar av olika ord.

Parser

L ${\displaystyle LL(k)}-$ parsern är en deterministisk pushdown-automat med förmågan att kika på nästa $k$ inmatningssymboler utan att läsa Denna tittförmåga kan emuleras genom att lagra lookahead-buffertens innehåll i det ändliga tillståndsutrymmet, eftersom både buffert- och inmatningsalfabetet är ändliga i storlek. Som ett resultat gör detta inte automaten mer kraftfull, utan är en bekväm abstraktion.

Stackalfabetet är ${\displaystyle \Gamma =N\cup \Sigma } ,$ där:

$N$ är uppsättningen icke-terminaler;
$\Sigma$ uppsättningen terminal (ingång) symboler med en speciell end-of-input (EOI) symbol $\$$ .

Parserstacken innehåller initialt startsymbolen ovanför EOI: $[\ S\ \$\ ]$ . Under drift ersätter parsern upprepade gånger symbolen $X$ ovanpå stacken:

med lite $\alpha$ , om $X\in N$ och det finns en regel $X\to \alpha$ ;
med $\epsilon$ (i vissa beteckningar $\lambda$ ), dvs. $X$ tas bort från stacken, om $X\in \Sigma$ . I det här fallet läses en inmatningssymbol ${\displaystyle x} och om$ $x\neq X$ avvisar analysatorn inmatningen.

Om den sista symbolen som ska tas bort från stacken är EOI, är analysen framgångsrik; automaten accepterar via en tom stack.

Tillstånden och övergångsfunktionen ges inte explicit; de specificeras (genereras) med hjälp av en mer bekväm analystabell istället. Tabellen ger följande mappning:

rad: symbol överst i stack $X$
kolumn: $|w|\leq k$ lookahead buffertinnehåll
cell: regelnummer för $X\to \alpha$ eller $\epsilon$

Om analysatorn inte kan utföra en giltig övergång, avvisas inmatningen (tomma celler). För att göra tabellen mer kompakt visas vanligtvis endast rader som inte är terminaler, eftersom åtgärden är densamma för terminaler.

Konkret exempel

Uppstart

För att förklara hur en LL(1)-parser fungerar kommer vi att överväga följande lilla LL(1)-grammatik:

S → F
S → (S + F)
F → a

och analysera följande indata:

(a + a)

En LL(1)-tolkningstabell för en grammatik har en rad för var och en av icke-terminalerna och en kolumn för varje terminal (inklusive den speciella terminalen, representerad här som $ , som används för att indikera slutet av ingångsströmmen ) .

Varje cell i tabellen kan peka på högst en regel i grammatiken (identifierad med dess nummer). Till exempel, i analystabellen för ovanstående grammatik pekar cellen för det icke-terminala 'S' och terminalen '(' på regel nummer 2:

	(	)	a	+	$
S	2	—	1	—	—
F	—	—	3	—	—

Algoritmen för att konstruera en analystabell beskrivs i ett senare avsnitt, men låt oss först se hur parsern använder analystabellen för att bearbeta dess input.

Parsingprocedur

I varje steg läser parsern nästa tillgängliga symbol från inmatningsströmmen och den översta symbolen från stacken. Om ingångssymbolen och stack-top-symbolen matchar, kasserar parsern dem båda, och lämnar endast de omatchade symbolerna i inmatningsströmmen och på stacken.

Sålunda, i sitt första steg, läser tolken inmatningssymbolen ' ( ' och stack- top -symbolen 'S'. Instruktionen för analystabellen kommer från kolumnen med ingångssymbolen ' ( ' och raden med stack- toppsymbolen 'S'; den här cellen innehåller '2', som instruerar tolkaren att tillämpa regel (2). Parseraren måste skriva om 'S' till ' ( S + F ) ' på stacken genom att ta bort 'S' från stacken och trycka ')', 'F', '+', 'S', '(' på stacken, och detta skriver regel nummer 2 till utgången. Stacken sedan blir:

 [  (  , S,  +  , F,  )  ,  $  ]

I det andra steget tar parsern bort ' ( ' från sin indataström och från sin stack, eftersom de nu matchar. Stacken blir nu:

 [S,  +  , F,  )  ,  $  ]

Nu har parsern ett ' a' på sin ingångsström och ett 'S' som stacktop. Analystabellen instruerar den att tillämpa regel (1) från grammatiken och skriva regelnummer 1 till utdataströmmen. Stacken blir:

 [ F,  +  , F,  )  ,  $  ]

Parsern har nu ett ' a' på sin ingångsström och ett 'F' som sin stacktop. Analystabellen instruerar den att tillämpa regel (3) från grammatiken och skriva regelnummer 3 till utdataströmmen. Stacken blir:

 [  a  ,  +  , F,  )  ,  $  ]

Parsern har nu ett ' a' på ingångsströmmen och ett 'a' överst på högen. Eftersom de är lika, tar den bort den från inmatningsströmmen och skjuter upp den från toppen av stacken. Parsern har sedan ett ' +' på ingångsströmmen och '+' är överst i stacken, vilket betyder, som med 'a', att den tas bort från stacken och tas bort från inmatningsströmmen. Detta resulterar i:

 [F,  )  ,  $  ]

I de kommande tre stegen kommer parsern att ersätta ' F' på stacken med ' a' , skriva regelnummer 3 till utgångsströmmen och ta bort ' a' och ' )' från både stacken och ingångsströmmen. Parsern slutar alltså med ' $' på både sin stack och sin ingångsström.

I det här fallet kommer parsern att rapportera att den har accepterat inmatningssträngen och skriva följande lista med regelnummer till utdataströmmen:

[ 2, 1, 3, 3 ]

Detta är verkligen en lista med regler för en härledning längst till vänster av inmatningssträngen, vilket är:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

Parserimplementering i C++

Nedan följer en C++-implementering av en tabellbaserad LL-parser för exempelspråket:

 
 
 

  
	
	
		
		
			
		
			
		

	
			
	 #include  <iostream>  #include  <map>  #include  <stack>  enum  Symboler  {  // symbolerna:  // Terminalsymboler:  TS_L_PARENS  ,  // (  TS_R_PARENS  ,  // )  TS_A  ,  // a  TS_PLUS  ,  // +  TS_EOS  ,  // $, i detta fall motsvarar '\0'  TS_INVALID  ,  // ogiltig token  // Icke-terminalsymboler:  NTS_S  ,  // S  NTS_F 		





  

	 
	
		    
		    
		    
		    // F  };  /*  Konverterar en giltig token till motsvarande terminalsymbol  */  Symboler  lexer  (  char  c  )  {  switch  (  c  )  {  case  '('  :  return  TS_L_PARENS  ;  case  ')'  :  return  TS_R_PARENS  ;  case  'a'  :  returnera  TS_A  ;  case  '+'  :  returnera  
		    
		    
	


    

	  

	   
	
		   TS_PLUS  ;  fall  '\0'  :  returnera  TS_EOS  ;  // end of stack: $-terminalsymbolen  standard  :  return  TS_INVALID  ;  }  }  int  main  (  int  argc  ,  char  **  argv  )  {  använder  namnutrymme  std  ;  if  (  argc  <  2  )  {  cout  <<  "användning:  \n\t   
		 0
	

	
	     
			
	 	

	
	 ll '(a+a)'"  <<  endl  ;  return  ;  }  // LL parsertabell, mappar < non-terminal, terminal> par till action  map  <  Symbols  ,  map  <  Symbols  ,  int  >  >  table  ;  stack  <  Symbols  >  ss  ;  // symbol stack  char  *  p  ;  // input buffer  // initiera symbolerna stack  ss  . 	
			

	
	  0

	
	  
	  
	 push  (  TS_EOS  );  // terminal, $  ss  .  push  (  NTS_S  );  // icke-terminal, S  // initiera symbolströmmarkören  p  =  &  argv  [  1  ][  ];  //  ställ in analystabellstabellen  [  NTS_S  ][  TS_L_PARENS  ]  =  2  ;  tabell  [  NTS_S  ][  TS_A  ]  =  1  ;  tabell   

	   0
	
		   
		
			      
			
			 [  NTS_F  ][  TS_A  ]  =  3  ;  while  (  ss  .  size  ()  >  )  {  if  (  lexer  (  *  p  )  ==  ss  .  top  ())  {  cout  <<  "Matchade symboler: "  <<  lexer  (  *  p  )  <<  endl  ;  p  ++  ;  ss 
		
		
		
			      
			 
			
				 	
					 .  pop  ();  }  else  {  cout  <<  "Regel"  <<  tabell  [  ss  .  top  ()][  lexer  (  *  p  )]  <<  endl  ;  switch  (  tabell  [  ss  .  top  ()][  lexer  (  *  p  )])  {  fall  1  :  // 1. S → F  ss  .  pop 
						
					

				 	
					
						
							
						
							 ();  ss  .  push  (  NTS_F  );  // F  paus  ;  fall  2  :  // 2. S → (S + F)  ss  .  pop  ();  ss  .  push  (  TS_R_PARENS  );  //)  ss  .  push  (  NTS_F  );  // F  ss  .  push  (  TS_PLUS  );  // +  ss  .  push  (  NTS_S  );  // S 
						
					

				 	
					
						
					

				
					    
					 0
			
		
	

	  ss  .  push  (  TS_L_PARENS  );  // (  break  ;  fall  3  :  // 3. F → a  ss  .  pop  ();  ss  .  push  (  TS_A  );  // a  break  ;  default  :  cout  <<  "parsing table defaulted"  <<  endl  ;  return  ;  }  }  }  cout  <<    

	 0
 "avslutad analys"  <<  endl  ;  återvända  ;  }

Parserimplementering i Python


  0
  


  0
  
  
  
  
  


  0
  


     0   # Alla konstanter indexeras från 0  TERM  =  REGEL  =  1  # Terminaler  T_LPAR  =  T_RPAR  =  1  T_A  =  2  T_PLUS  =  3  T_END  =  4  T_INVALID  =  5  # Non-Terminals  N_S  =  N_F  =  1  # Parse tabelltabell  =  [  [  1  ,  -  1  ,  ,  -  1  ,  -  1  
              

   
                  ,  -  1  ],  [  -  1  ,  -  1  ,  2  ,  -  1  ,  -  1  ,  -  1  ]]  REGLER  =  [[(  REGEL  ,  N_F  )],  [(  TERM  ,  T_LPAR  ),  (  REGEL  ,  N_S  ),  (  TERM  ,  T_PLUS  ),  (  RULE  ,  N_F  ),  (  
          

     

 
    
      
       
              TERM  ,  T_RPAR  )],  [(  TERM  ,  T_A  )]]  stack  =  [(  TERM  ,  T_END  ),  (  RULE  ,  N_S  )]  def  lexical_analysis  (  inputstring  ):  print  (  "Lexical analysis")  tokens  =  [  ]  för  c  i  inputstring  :  if  c  ==  "+"  :  
            
            
            
          tokens  .  append  (  T_PLUS  )  elif  c  ==  "("  :  tokens  .  append  (  T_LPAR  )  elif  c  ==  ")"  :  tokens  .  append  (  T_RPAR  )  elif  c  ==  "a"  :  tokens  .  append  (  T_A  )  annat  :  tokens  .  bifoga 
    
    
     

 
    
      0
       0
            (  T_INVALID  )  tokens  .  append  (  T_END  )  print  (  tokens  )  return  tokens  def  syntactic_analysis  (  tokens  ):  print  (  "Syntaktisk analys"  )  position  =  medan  len  (  stack  )  >  :  (  stype  ,  svalue  )  =  stack  .  pop  () 
          
           
               
                  
                 
                   
                    
            
                  token  =  tokens  [  position  ]  if  stype  ==  TERM  :  if  svalue  ==  token  :  position  +=  1  print  (  "pop"  ,  svalue  )  if  token  ==  T_END  :  print  (  "input accepted"  )  else  :  print  (  "bad term vid inmatning:"  ,  token  ) 
                
           
               
              
             
               
                 break  elif  stype  ==  REGEL  :  print  (  "svalue"  ,  svalue  ,  "token"  ,  token  )  regel  =  tabell  [  svalue  ][  token  ]  print  (  "  regel"  ,  regel  )  för  r  omvänt  (  REGLER  [  regel  ]):  stack  .  lägga till  (  r 
         

  
 )  print  (  "stack"  ,  stack  )  inputstring  =  "(a+a)"  syntactic_analysis  (  lexical_analysis  (  inputstring  ))

Anmärkningar

Som framgår av exemplet utför parsern tre typer av steg beroende på om toppen av stacken är en icke-terminal, en terminal eller specialsymbolen $ :

Om toppen är en icke-terminal, så letar parsern upp i analystabellen, på basis av denna icke-terminal och symbolen på ingångsströmmen, vilken regel i grammatiken den ska använda för att ersätta icke-terminal på stacken. Regelns nummer skrivs till utgångsströmmen. Om analystabellen indikerar att det inte finns någon sådan regel rapporterar parsern ett fel och stoppar.
Om toppen är en terminal jämför parsern den med symbolen på ingångsströmmen och om de är lika tas de båda bort. Om de inte är lika rapporterar parsern ett fel och stoppar.
Om toppen är $ och på ingångsströmmen finns det också en $ så rapporterar parsern att den framgångsrikt har analyserat ingången, annars rapporterar den ett fel. I båda fallen kommer tolken att stoppa.

Dessa steg upprepas tills tolken slutar, och sedan kommer den antingen att ha analyserat ingången fullständigt och skrivit en härledning längst till vänster till utgångsströmmen eller så kommer den att ha rapporterat ett fel.

Konstruera en LL(1)-analystabell

För att fylla analystabellen måste vi fastställa vilken grammatikregel som analyseraren ska välja om den ser en icke-terminal A på toppen av sin stack och en symbol a på sin ingångsström. Det är lätt att se att en sådan regel bör ha formen A → w och att språket som motsvarar w bör ha minst en sträng som börjar med a . För detta ändamål definierar vi den första uppsättningen av w , skriven här som Fi ( w ), som den uppsättning terminaler som kan hittas i början av någon sträng i w , plus ε om den tomma strängen också tillhör w . Med en grammatik med reglerna A ₁ → w ₁ , …, A _n → w _n , kan vi beräkna Fi ( w _i ) och Fi ( A _i ) för varje regel enligt följande:

initiera varje Fi ( A _i ) med den tomma uppsättningen
lägg till Fi( w _i ) till Fi ( A _i ) för varje regel A _i → w _i , där Fi definieras enligt följande:
- Fi( aw' ) = { a } för varje terminal a
- Fi( Aw' ) = Fi ( A ) för varje icke-terminal A med ε inte i Fi ( A )
- Fi( Aw' ) = ( Fi ( A ) \ { ε }) ∪ Fi( w' ) för varje icke-terminal A med ε i Fi ( A )
- Fi(ε) = { ε }
lägg till Fi( w _i ) till Fi ( A _i ) för varje regel A _i → w _i
gör steg 2 och 3 tills alla Fi- uppsättningar förblir desamma.

Resultatet är den minsta fixpunktslösningen för följande system:

Fi ( A ) ⊇ Fi ( w ) för varje regel A → w
Fi ( a ) ⊇ { a }, för varje terminal a
₀ ₀₀ Fi ( w w ₁ ) ⊇ Fi ( w )· Fi ( w ₁ ), för alla ord w och w ₁
Fi (ε) ⊇ {ε}

där, för uppsättningar av ord U och V, den trunkerade produkten definieras av $U\cdot V=\{(uv): 1:u\in U,v\in V\}$ , och w:1 betecknar det initiala längd-1-prefixet för ord w med längden 2 eller mer, eller w, självt, om w har längden 0 eller 1.

Tyvärr räcker inte First-seten för att beräkna analystabellen. Detta beror på att en höger sida w av en regel i slutändan kan skrivas om till den tomma strängen. Så parsern bör också använda regeln A → w om ε är i Fi ( w ) och den ser på ingångsströmmen en symbol som kan följa A . Därför behöver vi också följa uppsättningen av A , skriven som Fo ( A ) här, vilket definieras som uppsättningen av terminaler a så att det finns en sträng av symboler αAaβ som kan härledas från startsymbolen. Vi använder $ som en speciell terminal som indikerar slutet på ingångsströmmen och S som startsymbol.

Att beräkna följuppsättningarna för icke-terminalerna i en grammatik kan göras på följande sätt:

initialisera Fo ( S ) med { $ } och varannan Fo ( A _i ) med den tomma uppsättningen
om det finns en regel av formen A _j → wA _i w' , då
- om terminalen a är i Fi ( w' ), lägg sedan till a till Fo ( A _i )
- om ε är i Fi ( w' ), lägg sedan till Fo ( A _j ) till Fo ( A _i )
- om w' har längden 0, lägg sedan till Fo ( A _j ) till Fo ( A _i )
upprepa steg 2 tills alla Fo- uppsättningar förblir desamma.

Detta ger den minsta fixpunktslösningen till följande system:

Fo ( S ) ⊇ { $ }
Fo ( A ) ⊇ Fi ( w )· Fo ( B ) för varje regel av formen B → ... A w

Nu kan vi definiera exakt vilka regler som ska visas var i analystabellen. Om T [ A , a ] betecknar posten i tabellen för icke terminal A och terminal a , då

T [ A , a ] innehåller regeln A → w om och endast om

a är i Fi ( w ) eller

ε är i Fi ( w ) och a är i Fo ( A ).

Motsvarande: T [ A , a ] innehåller regeln A → w för varje a ∈ Fi ( w )· Fo ( A ).

Om tabellen innehåller högst en regel i var och en av dess celler, kommer analysatorn alltid att veta vilken regel den måste använda och kan därför analysera strängar utan att backa. Det är i just detta fall som grammatiken kallas en LL (1) grammatik .

Konstruera en LL( k )-analystabell

Konstruktionen för LL(1)-tolkare kan anpassas till LL( k ) för k > 1 med följande modifieringar:

den trunkerade produkten definieras $U\cdot V=\{(uv):1:u\in U,v\in V \}$ , där w:k anger det initiala längd-k-prefixet för ord med längden > k, eller w, självt, om w har längden k eller mindre,
Fo ( S ) = { $ ^k }
Tillämpa Fi (αβ) = Fi (α) $\cdot$ Fi (β) även i steg 2 av Fi -konstruktionen som ges för LL(1).
I steg 2 av Fo -konstruktionen, för A _j → wA _i w' lägg helt enkelt till Fi ( w' ) $\cdot$ Fo ( A _{j )} till Fo ( A _i ).

där en indata suffixeras med k slutmarkörer $ , för att fullt ut redogöra för k lookahead-kontexten. Detta tillvägagångssätt eliminerar specialfall för ε och kan tillämpas lika väl i LL(1)-fallet.

Fram till mitten av 1990-talet ansågs det allmänt att LL( k )-analys (för k > 1) var opraktisk, ^{[ citat behövs ]} eftersom analystabellen skulle ha exponentiell storlek i k i värsta fall. Denna uppfattning förändrades gradvis efter lanseringen av Purdue Compiler Construction Tool Set runt 1992, då det visades att många programmeringsspråk kan analyseras effektivt av en LL( k ) ) parser utan att utlösa parserns värsta tänkbara beteende. Dessutom är LL-parsning i vissa fall möjlig även med obegränsad framsyn. använder traditionella parsergeneratorer som yacc LALR(1) parsertabeller för att konstruera en begränsad LR-parser med en fast lookahead med en token.

Konflikter

Som beskrivits i inledningen känner LL(1)-tolkarna igen språk som har LL(1)-grammatik, vilket är ett specialfall av sammanhangsfria grammatiker; LL(1)-tolkare kan inte känna igen alla sammanhangsfria språk. LL(1)-språken är en riktig delmängd av LR(1)-språken, som i sin tur är en riktig delmängd av alla sammanhangsfria språk. För att en sammanhangsfri grammatik ska vara en LL(1) grammatik får inte vissa konflikter uppstå, vilket vi beskriver i detta avsnitt.

Terminologi

Låt A vara en icke-terminal. FIRST( A ) är (definierad att vara) den uppsättning terminaler som kan visas i den första positionen av vilken sträng som helst härledd från A . FÖLJ( A ) är facket över:

FIRST( B ) där B är valfri icke-terminal som omedelbart följer efter A på höger sida av en produktionsregel .
FOLLOW( B ) där B är vilket huvud som helst av en regel av formen B → wA .

LL(1) konflikter

Det finns två huvudtyper av LL(1)-konflikter:

FÖRSTA/FÖRSTA konflikt

De FÖRSTA uppsättningarna av två olika grammatikregler för samma icke-terminala skärning. Ett exempel på en LL(1) FIRST/FIRST konflikt:

S -> E | E 'a' E -> 'b' | ε

FIRST( E ) = { b , ε} och FIRST( E a ) = { b , a }, så när tabellen ritas uppstår en konflikt under terminal b i produktionsregeln S .

Specialfall: vänsterrekursion

Vänsterrekursion kommer att orsaka en FIRST/FIRST-konflikt med alla alternativ.

E -> E '+' term | alt1 | alt2

FÖRSTA/FÖLJ konflikt

FIRST och FOLLOW uppsättningen av en grammatikregel överlappar varandra. Med en tom sträng (ε) i den FÖRSTA uppsättningen är det okänt vilket alternativ som ska väljas. Ett exempel på en LL(1)-konflikt:

S -> A 'a' 'b' A -> 'a' | ε

Den FÖRSTA uppsättningen av A är { a , ε}, och FÖLJ-mängden är { a }.

Lösningar på LL(1)-konflikter

Vänster factoring

En vanlig vänsterfaktor är "factored out".

A -> X | XYZ

blir

A -> XB B -> YZ | ε

Kan tillämpas när två alternativ börjar med samma symbol som en FÖRSTA/FÖRSTA konflikt.

Ett annat exempel (mer komplext) med ovanstående FIRST/FIRST konfliktexempel:

S -> E | E 'a' E -> 'b' | ε

blir (sammanslagna till en enda icke-terminal)

S -> 'b' | ε | 'b' 'a' | 'a'

sedan genom vänsterfaktorering, blir

S -> 'b' E | E E -> 'a' | ε

Utbyte

Ersätter en regel med en annan regel för att ta bort indirekta eller FIRST/FOLLOW-konflikter. Observera att detta kan orsaka en FIRST/FIRST-konflikt.

Vänsterrekursionsborttagning

Ser.

För en allmän metod, se ta bort vänsterrekursion . Ett enkelt exempel för borttagning av vänsterrekursion: Följande produktionsregel har lämnat rekursion på E

E -> E '+' T E -> T

Denna regel är inget annat än en lista över T:n separerade med '+'. I ett reguljärt uttryck form T ('+' T)*. Så regeln skulle kunna skrivas om som

E -> TZ Z -> '+' TZ Z -> ε

Nu finns det ingen vänsterrekursion och inga konflikter på någon av reglerna.

Men inte alla sammanhangsfria grammatiker har en likvärdig LL(k)-grammatik, t.ex.

S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε

Det kan visas att det inte finns någon LL(k)-grammatik som accepterar språket som genereras av denna grammatik.

Se även

Anteckningar

^ Rosenkrantz, DJ; Stearns, RE (1970). "Egenskaper för deterministiska top-down grammatiker" . Information och kontroll . 17 (3): 226–256. doi : 10.1016/s0019-9958(70)90446-8 .
^ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-vanliga grammatiker". Instytutu Maszyn Matematycznych : 107–119.
^ Jarzabek, Stanislav; Krawczyk, Tomasz (nov 1975). "LL-vanliga grammatiker" . Informationsbehandlingsbrev . 4 (2): 31–37. doi : 10.1016/0020-0190(75)90009-5 .
^ David A. Poplawski (aug 1977). Egenskaper för LL-Regular Languages (Teknisk rapport). Purdue University , Institutionen för datavetenskap.
^ Parr, Terence och Fisher, Kathleen (2011). "LL (*) grunden för ANTLR-parsergeneratorn". ACM SIGPLAN-meddelanden . 46 (6): 425–436. doi : 10.1145/1993316.1993548 . {{ citera tidskrift }} : CS1 underhåll: flera namn: lista över författare ( länk )
^ Belcak, Peter (2020). "LL(finita)-analysstrategin för optimal LL(k)-analys". arXiv : 2010.07874 [ cs.PL ].
^ Ford, Bryan (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation". ACM SIGPLAN-meddelanden . doi : 10.1145/982962.964011 .
^ Pat Terry (2005). Kompilera med C# och Java . Pearson utbildning. s. 159–164. ISBN 9780321263605 .
^ William M. Waite och Gerhard Goos (1984). Kompilatorkonstruktion . Texter och monografier i datavetenskap. Heidelberg: Springer. ISBN 978-3-540-90821-0 . Här: Sekt. 5.3.2, sid. 121-127; i synnerhet, sid. 123.
^ Richard E. Stearns och PM Lewis (1969). "Egendomsgrammatik och bordsmaskiner" . Information och kontroll . 14 (6): 524–549. doi : 10.1016/S0019-9958(69)90312-X .
^ "LL Grammars" (PDF) . Arkiverad (PDF) från originalet 2010-06-18 . Hämtad 2010-05-11 .
^ Modern kompilatordesign , Grune, Bal, Jacobs och Langendoen

externa länkar

En handledning om implementering av LL(1)-parsers i C# (arkiverad)
Parsing Simulator Denna simulator används för att generera analystabeller LL(1) och för att lösa övningarna i boken.
LL(1) DSL PEG-parser (verktygssatsramverk)
Språkteoretisk jämförelse av LL- och LR-grammatik
LL(k) Parsing Theory

[1] Rosenkrantz, DJ; Stearns, RE (1970). "Egenskaper för deterministiska top-down grammatiker" . Information och kontroll . 17 (3): 226–256. doi : 10.1016/s0019-9958(70)90446-8 .

[2] Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "LL-vanliga grammatiker". Instytutu Maszyn Matematycznych : 107–119.

[3] Jarzabek, Stanislav; Krawczyk, Tomasz (nov 1975). "LL-vanliga grammatiker" . Informationsbehandlingsbrev . 4 (2): 31–37. doi : 10.1016/0020-0190(75)90009-5 .

[4] David A. Poplawski (aug 1977). Egenskaper för LL-Regular Languages (Teknisk rapport). Purdue University , Institutionen för datavetenskap.

[5] Parr, Terence och Fisher, Kathleen (2011). "LL (*) grunden för ANTLR-parsergeneratorn". ACM SIGPLAN-meddelanden . 46 (6): 425–436. doi : 10.1145/1993316.1993548 . {{ citera tidskrift }} : CS1 underhåll: flera namn: lista över författare ( länk )

[6] Belcak, Peter (2020). "LL(finita)-analysstrategin för optimal LL(k)-analys". arXiv : 2010.07874 [ cs.PL ].

[7] Ford, Bryan (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation". ACM SIGPLAN-meddelanden . doi : 10.1145/982962.964011 .

[8] Pat Terry (2005). Kompilera med C# och Java . Pearson utbildning. s. 159–164. ISBN 9780321263605 .

[9] William M. Waite och Gerhard Goos (1984). Kompilatorkonstruktion . Texter och monografier i datavetenskap. Heidelberg: Springer. ISBN 978-3-540-90821-0 . Här: Sekt. 5.3.2, sid. 121-127; i synnerhet, sid. 123.

[10] Richard E. Stearns och PM Lewis (1969). "Egendomsgrammatik och bordsmaskiner" . Information och kontroll . 14 (6): 524–549. doi : 10.1016/S0019-9958(69)90312-X .

[11] "LL Grammars" (PDF) . Arkiverad (PDF) från originalet 2010-06-18 . Hämtad 2010-05-11 .

[12] Modern kompilatordesign , Grune, Bal, Jacobs och Langendoen

Parsningsalgoritmer
Uppifrån och ner	LL Rekursiv härkomst Svans rekursiv
Botten upp	Företräde Enkel Operatör Rangergård LR Enkel Se framåt Kanonisk Generaliserad CYK Rekursiv uppstigning Skift-minska
Blandat, annat	Kombinator Diagram Earley
Relaterade ämnen	PINNE Definitiv klausul grammatik Deterministisk analys Dynamisk programmering Memoisering Parsergenerator LALR Analysera träd AST Parsning utan skanner Historia om kompilatorkonstruktion Jämförelse av parsergeneratorer Operatörspreferensgrammatik