Analizator LL - LL parser

În informatică , un analizor LL (de la stânga la dreapta, derivarea din stânga) este un analizator de sus în jos pentru un limbaj restricționat fără context . Analizează de intrare de la L TEF la dreapta, efectuarea L eftmost derivare a sentinței.

Un analizor LL se numește analizor LL ( k ) dacă folosește k jetoane de lookahead atunci când analizează o propoziție. O gramatică se numește o gramatică LL ( k ) dacă un analizor LL ( k ) poate fi construit din ea. Un limbaj formal se numește un limbaj LL ( k ) dacă are o gramatică LL ( k ). Setul de limbi LL ( k ) este conținut în mod corespunzător în cel al limbilor LL ( k +1), pentru fiecare k ≥ 0. Un corolar al acestui fapt este că nu toate limbile fără context pot fi recunoscute de un analizor LL ( k ) .

Un analizor LL se numește LL-regular dacă analizează exact clasa limbilor LL-regular . Gramaticile LLR sunt un superset adecvat al gramaticilor LL (k) pentru orice k. Pentru fiecare gramatică LLR există un analizor LLR care analizează gramatica în timp liniar.

Două tipuri de parseruri nomenclative externe sunt LL (*) și LL (finit). Un analizor se numește LL (*) / LL (finit) dacă folosește strategia de analiză LL (*) / LL (finită). Analizoarele LL (*) și LL (finite) sunt funcțional mai asemănătoare cu analizoarele PEG . Un analizor LL (finit) poate analiza în mod optim o gramatică LL (k) arbitrară în cantitatea de comparații lookahead și lookahead. Clasa gramaticilor analizate de strategia LL (*) cuprinde unele limbaje sensibile la context datorită utilizării predicatelor sintactice și semantice și nu a fost identificată. S-a sugerat că analizatorii LL (*) sunt considerați mai bine ca analizori TDPL . Împotriva concepției greșite populare, analizorii LL (*) nu sunt LLR în general și sunt garantați de construcție pentru a obține performanțe mai slabe în medie (super-liniar împotriva timpului liniar) și mult mai slabe în cel mai rău caz (exponențial împotriva timpului liniar).

Gramaticile LL, în special gramaticile LL (1), prezintă un mare interes practic, întrucât analizatorii pentru aceste gramatici sunt ușor de construit și multe limbaje de calculator sunt concepute pentru a fi LL (1) din acest motiv. Analizatoarele LL sunt analizoare pe bază de tabel, similare cu analizoarele LR . Gramaticile LL pot fi, de asemenea, analizate de analizoare descendente recursive . Conform lui Waite și Goos (1984), gramaticile LL ( k ) au fost introduse de Stearns și Lewis (1969).

Prezentare generală

Pentru o gramatică fără context dată , analizorul încearcă să găsească cea mai stângă derivare . Având un exemplu de gramatică : ${\ displaystyle G}$

${\ displaystyle S \ to E}$
${\ displaystyle E \ to (E + E)}$
${\ displaystyle E \ to i}$

cea mai stânga derivare pentru este: ${\ displaystyle w = ((i + i) + i)}$

{\ displaystyle 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)}

În general, există mai multe posibilități atunci când selectați o regulă pentru a extinde cel mai stâng non-terminal. În pasul 2 al exemplului anterior, analizorul trebuie să aleagă dacă se aplică regula 2 sau regula 3:

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

Pentru a fi eficient, analizorul trebuie să fie capabil să facă această alegere în mod determinist, atunci când este posibil, fără a urmări înapoi. Pentru unele gramatici, acest lucru poate face acest lucru aruncând o privire pe intrarea necitită (fără citire). În exemplul nostru, dacă analizorul știe că următorul simbol necitit este , singura regulă corectă care poate fi utilizată este 2. ${\ displaystyle (}$

În general, un analizor poate privi înainte simbolurile. Cu toate acestea, având în vedere o gramatică, problema determinării dacă există un parser pentru unii care o recunoaște este indecidabilă. Pentru fiecare , există un limbaj care nu poate fi recunoscut de un analizor, dar poate fi de un . ${\ displaystyle LL (k)}$ ${\ displaystyle k}$ ${\ displaystyle LL (k)}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle LL (k)}$ ${\ displaystyle LL (k + 1)}$

Putem folosi analiza de mai sus pentru a da următoarea definiție formală:

Să fie o gramatică fără context și . Spunem că este , dacă și numai dacă pentru oricare două derivări din stânga: ${\ displaystyle G}$ ${\ displaystyle k \ geq 1}$ ${\ displaystyle G}$ ${\ displaystyle LL (k)}$

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

are următoarea condiție: prefixul șirului de lungime este egal cu prefixul șirului de lungime implică . ${\ displaystyle u}$ ${\ displaystyle k}$ ${\ displaystyle v}$ ${\ displaystyle k}$ ${\ displaystyle \ beta \ = \ \ gamma}$

În această definiție, este simbolul de pornire și orice non-terminal. Intrarea deja derivată , dar necitită și sunt șiruri de terminale. Literele grecești , și reprezintă orice șir de ambele terminale și non-terminale (eventual gol). Lungimea prefixului corespunde dimensiunii bufferului lookahead, iar definiția spune că acest buffer este suficient pentru a distinge între oricare două derivări ale cuvintelor diferite. ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle w}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ beta}$ ${\ displaystyle \ gamma}$

Analizator

Parserul este un automaton pushdown deterministe cu abilitatea de a arunca o privire asupra următoarelor simboluri de intrare fără a citi. Această capacitate de vizualizare poate fi emulată prin stocarea conținutului tampon lookahead în spațiul de stare finită, deoarece atât bufferul, cât și alfabetul de intrare au dimensiuni finite. Ca urmare, acest lucru nu face automatul mai puternic, ci este o abstractizare convenabilă. ${\ displaystyle LL (k)}$ ${\ displaystyle k}$

Alfabetul stivei este , unde: ${\ displaystyle \ Gamma = N \ cup \ Sigma}$

${\ displaystyle N}$ este setul de non-terminale;
${\ displaystyle \ Sigma}$ setul de simboluri terminale (de intrare) cu un simbol special de sfârșit de intrare (EOI) . ${\ displaystyle \ $}$

Stiva interpretor inițial conține simbolul de pornire deasupra EOI: . În timpul funcționării, analizorul înlocuiește în mod repetat simbolul de deasupra stivei: ${\ displaystyle [\ S \ \ $ \]}$ ${\ displaystyle X}$

cu unele , dacă și există o regulă ; ${\ displaystyle \ alpha}$ ${\ displaystyle X \ în N}$ ${\ displaystyle X \ to \ alpha}$
cu (în unele notații ), adică este scos din stivă, dacă . În acest caz, se citește un simbol de intrare și dacă , parserul respinge intrarea. ${\ displaystyle \ epsilon}$ ${\ displaystyle \ lambda}$ ${\ displaystyle X}$ ${\ displaystyle X \ in \ Sigma}$ ${\ displaystyle x}$ ${\ displaystyle x \ neq X}$

Dacă ultimul simbol care trebuie eliminat din stivă este EOI, analiza are succes; automatul acceptă printr-o stivă goală.

Stările și funcția de tranziție nu sunt date în mod explicit; sunt specificate (generate) folosind în schimb un tabel de analiză mai convenabil . Tabelul oferă următoarea mapare:

rând: simbolul partea de sus a stivei ${\ displaystyle X}$
coloană: conținut tampon lookahead ${\ displaystyle | w | \ leq k}$
celula: numărul regulii pentru sau ${\ displaystyle X \ to \ alpha}$ ${\ displaystyle \ epsilon}$

Dacă analizorul nu poate efectua o tranziție validă, intrarea este respinsă (celule goale). Pentru a face tabelul mai compact, sunt afișate în mod obișnuit doar rândurile non-terminale, deoarece acțiunea este aceeași pentru terminale.

Exemplu concret

Înființat

Pentru a explica funcționarea unui analizor LL (1), vom lua în considerare următoarea gramatică mică LL (1):

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

și analizați următoarea intrare:

(a + a)

Un tabel de analiză LL (1) pentru o gramatică are un rând pentru fiecare dintre non-terminale și o coloană pentru fiecare terminal (inclusiv terminalul special, reprezentat aici ca $ , care este folosit pentru a indica sfârșitul fluxului de intrare).

Fiecare celulă a tabelului poate indica cel mult o regulă a gramaticii (identificată prin numărul său). De exemplu, în tabelul de analiză pentru gramatica de mai sus, celula pentru non-terminal „S” și terminal ”(„ indică regula numărul 2:

	(	)	A	+	$
S	2	-	1	-	-
F	-	-	3	-	-

Algoritmul pentru a construi o tabelă de analiză este descris într-o secțiune ulterioară, dar mai întâi să vedem cum analizatorul folosește tabelul de analiză pentru a-și procesa intrarea.

Procedura de analiză

În fiecare etapă, analizorul citește următorul simbol disponibil din fluxul de intrare și simbolul cel mai de sus din stivă. Dacă simbolul de intrare și simbolul stivei se potrivesc, analizorul le elimină pe amândouă, lăsând doar simbolurile de neegalat în fluxul de intrare și în stivă.

Astfel, în primul său pas, analizorul citește simbolul de intrare ' ( ' și simbolul de sus al stivei 'S'. Instrucțiunea tabelei de analiză provine din coloana condusă de simbolul de intrare ' ( ' și rândul condus de stivă- simbolul de sus „S”; această celulă conține „2”, care instruiește analizorul să aplice regula (2). Analizatorul trebuie să rescrie „S” în „ ( S + F ) ” în stivă, eliminând „S” din stivă și apăsând ')', 'F', '+', 'S', '(' pe stivă, iar aceasta scrie regula 2 la ieșire. Stiva devine apoi:

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

În al doilea pas, analizorul elimină „ ( ” din fluxul de intrare și din stiva, deoarece se potrivesc acum. Stiva devine acum:

[ S, +, F, ), $ ]

Acum analizorul are un „ a” pe fluxul său de intrare și un „S” ca stivă. Tabelul de analiză îi instruiește să aplice regula (1) din gramatică și să scrie regula 1 la fluxul de ieșire. Stiva devine:

[ F, +, F, ), $ ]

Analizatorul are acum un „ a” pe fluxul său de intrare și un „F” ca vârf de stivă. Tabelul de analiză îi instruiește să aplice regula (3) din gramatică și să scrie regula 3 la fluxul de ieșire. Stiva devine:

[ a, +, F, ), $ ]

Analizatorul are acum un „ a” pe fluxul de intrare și un „a” în partea superioară a stivei. Deoarece sunt la fel, îl elimină din fluxul de intrare și îl scoate din partea de sus a stivei. Analizatorul are apoi un „ +” pe fluxul de intrare și „+” se află în partea de sus a stivei, adică, cu „a”, este scos din stivă și eliminat din fluxul de intrare. Acest lucru are ca rezultat:

[ F, ), $ ]

În următorii trei pași, analizorul va înlocui „ F” din stivă cu „ a” , scrie regula numărul 3 în fluxul de ieșire și elimină „ a” și „ )” atât din stivă, cât și din fluxul de intrare. Analizatorul se termină astfel cu „ $” atât pe stiva, cât și pe fluxul de intrare.

În acest caz, analizorul va raporta că a acceptat șirul de intrare și va scrie următoarea listă de numere de reguli în fluxul de ieșire:

[2, 1, 3, 3]

Aceasta este într-adevăr o listă de reguli pentru o derivare din stânga a șirului de intrare, care este:

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

Implementarea analizorului în C ++

Mai jos urmează o implementare C ++ a unui analizor LL bazat pe tabel pentru limbajul de exemplu:

#include <iostream>
#include <map>
#include <stack>

enum Symbols {
	// the symbols:
	// Terminal symbols:
	TS_L_PARENS,	// (
	TS_R_PARENS,	// )
	TS_A,		// a
	TS_PLUS,	// +
	TS_EOS,		// $, in this case corresponds to '\0'
	TS_INVALID,	// invalid token

	// Non-terminal symbols:
	NTS_S,		// S
	NTS_F		// F
};

/*
Converts a valid token to the corresponding terminal symbol
*/
Symbols lexer(char c)
{
	switch (c)
	{
		case '(':  return TS_L_PARENS;
		case ')':  return TS_R_PARENS;
		case 'a':  return TS_A;
		case '+':  return TS_PLUS;
		case '\0': return TS_EOS; // end of stack: the $ terminal symbol
		default:   return TS_INVALID;
	}
}

int main(int argc, char **argv)
{
	using namespace std;

	if (argc < 2)
	{
		cout << "usage:\n\tll '(a+a)'" << endl;
		return 0;
	}

	// LL parser table, maps < non-terminal, terminal> pair to action
	map< Symbols, map<Symbols, int> > table;
	stack<Symbols>	ss;	// symbol stack
	char *p;	// input buffer

	// initialize the symbols stack
	ss.push(TS_EOS);	// terminal, $
	ss.push(NTS_S);		// non-terminal, S

	// initialize the symbol stream cursor
	p = &argv[1][0];

	// set up the parsing table
	table[NTS_S][TS_L_PARENS] = 2;
	table[NTS_S][TS_A] = 1;
	table[NTS_F][TS_A] = 3;

	while (ss.size() > 0)
	{
		if (lexer(*p) == ss.top())
		{
			cout << "Matched symbols: " << lexer(*p) << endl;
			p++;
			ss.pop();
		}
		else
		{
			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;
			switch (table[ss.top()][lexer(*p)])
			{
				case 1:	// 1. S → F
					ss.pop();
					ss.push(NTS_F);	// F
					break;

				case 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
					ss.push(TS_L_PARENS);	// (
					break;

				case 3:	// 3. F → a
					ss.pop();
					ss.push(TS_A);	// a
					break;

				default:
					cout << "parsing table defaulted" << endl;
					return 0;
			}
		}
	}

	cout << "finished parsing" << endl;

	return 0;
}

Implementarea analizorului în Python

# All constants are indexed from 0
TERM = 0
RULE = 1

# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5

# Non-Terminals
N_S = 0
N_F = 1

# Parse table
table = [[ 1, -1, 0, -1, -1, -1],
         [-1, -1, 2, -1, -1, -1]]

RULES = [[(RULE, N_F)],
         [(TERM, T_LPAR), (RULE, 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 = []
    for c in 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)
        else: tokens.append(T_INVALID)
    tokens.append(T_END)
    print(tokens)
    return tokens

def syntactic_analysis(tokens):
    print("Syntactic analysis")
    position = 0
    while len(stack) > 0:
        (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 on input:", token)
                break
        elif stype == RULE:
            print("svalue", svalue, "token", token)
            rule = table[svalue][token]
            print("rule", rule)
            for r in reversed(RULES[rule]):
                stack.append(r)
        print("stack", stack)

inputstring = "(a+a)"
syntactic_analysis(lexical_analysis(inputstring))

Observații

După cum se poate vedea din exemplu, analizorul efectuează trei tipuri de pași, în funcție de faptul dacă partea superioară a stivei este un non-terminal, un terminal sau simbolul special $ :

Dacă partea de sus este un nonterminal, atunci analizorul se uită în sus în tabelul de analiză, pe baza acestui nonterminal și a simbolului de pe fluxul de intrare, care regulă a gramaticii ar trebui să utilizeze pentru a înlocui nonterminal pe stivă. Numărul regulii este scris în fluxul de ieșire. Dacă tabelul de analiză indică faptul că nu există o astfel de regulă, analizorul raportează o eroare și se oprește.
Dacă partea de sus este un terminal, analizorul îl compară cu simbolul de pe fluxul de intrare și dacă sunt egali, sunt ambii eliminați. Dacă acestea nu sunt egale, analizorul raportează o eroare și se oprește.
Dacă partea de sus este $ și pe fluxul de intrare există și un $, atunci analizorul raportează că a analizat cu succes intrarea, în caz contrar raportează o eroare. În ambele cazuri, analizorul se va opri.

Acești pași se repetă până când parserul se oprește, apoi va fi fie analizat complet intrarea și scris o derivare din stânga în fluxul de ieșire, fie va fi raportat o eroare.

Construirea unui tabel de analiză LL (1)

Pentru a umple tabelul de analiză, trebuie să stabilim ce regulă gramaticală ar trebui să aleagă analizorul dacă vede un A nonterminal în partea de sus a stivei sale și un simbol a pe fluxul său de intrare. Este ușor de văzut că o astfel de regulă ar trebui să aibă forma A → w și că limba corespunzătoare lui w ar trebui să aibă cel puțin un șir începând cu a . În acest scop, definim primul set de w , scris aici ca Fi ( w ), ca setul de terminale care pot fi găsite la începutul unor șiruri în w , plus ε dacă șirul gol aparține și lui w . Având în vedere o gramatică cu regulile A ₁ → w ₁ , ..., A _n → w _n , putem calcula Fi ( w _i ) și Fi ( A _i ) pentru fiecare regulă după cum urmează:

inițializați fiecare Fi ( A _i ) cu setul gol
adăugați Fi ( w _i ) la Fi ( A _i ) pentru fiecare regulă A _i → w _i , unde Fi este definit după cum urmează:
- Fi ( aw ' ) = { a } pentru fiecare terminal a
- Fi ( Aw ' ) = Fi ( A ) pentru fiecare nonterminal A cu ε care nu este în Fi ( A )
- Fi ( Aw ' ) = ( Fi ( A ) \ {ε}) ∪ Fi ( w' ) pentru fiecare A nonterminal cu ε în Fi ( A )
- Fi (ε) = {ε}
adăugați Fi ( w _i ) la Fi ( A _i ) pentru fiecare regulă A _i → w _i
parcurgeți pașii 2 și 3 până când toate seturile Fi rămân la fel.

Rezultatul este cea mai mică soluție cu punct fix pentru următorul sistem:

Fi ( A ) ⊇ Fi ( w ) pentru fiecare regulă A → w
Fi ( a ) ⊇ { a }, pentru fiecare terminal a
Fi ( w ₀ w ₁ ) ⊇ Fi ( w ₀ ) · Fi ( w ₁ ), pentru toate cuvintele w ₀ și w ₁
Fi (ε) ⊇ {ε}

unde, pentru seturile de cuvinte U și V, produsul trunchiat este definit de și w: 1 denotă prefixul inițial lungime-1 al cuvintelor w de lungime 2 sau mai mare sau w, el însuși, dacă w are lungimea 0 sau 1. ${\ displaystyle U \ cdot V = \ {(uv): 1: u \ in U, v \ in V \}}$

Din păcate, primele seturi nu sunt suficiente pentru a calcula tabelul de analiză. Acest lucru se datorează faptului că partea dreaptă w a unei reguli ar putea fi în cele din urmă rescrisă în șirul gol. Deci , parser - ul ar trebui să utilizeze , de asemenea, regula A → w dacă ε este în Fi ( w ) și - l vede pe intrarea flux un simbol care ar putea urma o . Prin urmare, avem nevoie și de urmărirea lui A , scrisă ca Fo ( A ) aici, care este definită ca setul de terminale a astfel încât să existe un șir de simboluri αAaβ care poate fi derivat din simbolul de start. Folosim $ ca terminal special care indică sfârșitul fluxului de intrare și S ca simbol de pornire.

Calculul seturilor de urmărire pentru nonterminali dintr-o gramatică se poate face după cum urmează:

inițializați Fo ( S ) cu { $ } și orice alt Fo ( A _i ) cu setul gol
dacă există o regulă de forma A _j → wA _i w ' , atunci
- dacă terminalul a este în Fi ( w ' ), atunci adăugați un la Fo ( A _i )
- dacă ε este în Fi ( w ' ), atunci adăugați Fo ( A _j ) la Fo ( A _i )
- dacă w ' are lungimea 0, atunci adăugați Fo ( A _j ) la Fo ( A _i )
repetați pasul 2 până când toate seturile Fo rămân la fel.

Aceasta oferă soluția cu cel mai mic punct fix pentru următorul sistem:

Fo ( S ) ⊇ { $ }
Fo ( A ) ⊇ Fi ( w ) · Fo ( B ) pentru fiecare regulă a formei B → ... A w

Acum putem defini exact ce reguli vor apărea unde în tabelul de analiză. Dacă T [ A , a ] denotă intrarea în tabel pentru nonterminalul A și terminalul a , atunci

T [ A , a ] conține regula A → w dacă și numai dacă

a este în Fi ( w ) sau

ε este în Fi ( w ) și a este în Fo ( A ).

În mod echivalent: T [ A , a ] conține regula A → w pentru fiecare a ∈ Fi ( w ) · Fo ( A ).

Dacă tabelul conține cel mult o regulă în fiecare dintre celulele sale, atunci analizorul va ști întotdeauna ce regulă trebuie să utilizeze și, prin urmare, poate analiza șirurile fără a urmări înapoi. Este exact în acest caz , că gramatica se numește LL (1) gramatica .

Construirea unui tabel de analiză LL ( k )

Construcția pentru parserele LL (1) poate fi adaptată la LL ( k ) pentru k > 1 cu următoarele modificări:

se definește produsul trunchiat , unde w: k reprezintă lungimea inițială-k prefixul cuvintelor de lungime> k, sau w, el însuși, dacă w are lungimea k sau mai mică, ${\ displaystyle U \ cdot V = \ {(uv): 1: u \ in U, v \ in V \}}$
Fo ( S ) = { $ ^k }

unde o intrare este sufixată de k markeri $ , pentru a ține cont pe deplin de contextul k lookahead.

Până la mijlocul anilor 1990, se credea pe larg că analiza LL ( k ) (pentru k > 1) nu era practic, deoarece tabelul analizor ar avea dimensiunea exponențială în k în cel mai rău caz. Această percepție s-a schimbat treptat după lansarea Purdue Compiler Construction Tool Set în jurul anului 1992, când s-a demonstrat că multe limbaje de programare pot fi analizate eficient de un analizor LL ( k ) fără a declanșa cel mai rău comportament al analizatorului. Mai mult decât atât, în anumite cazuri, analiza LL este fezabilă chiar și cu un lookahead nelimitat. În schimb, generatoarele de parser tradiționale precum yacc folosesc tabele de parser LALR (1) pentru a construi un parser LR restricționat cu un lookahead fix cu un singur token.

Conflictele

Așa cum este descris în introducere, analizorii LL (1) recunosc limbile care au gramatici LL (1), care sunt un caz special al gramaticilor fără context; Analizatorii LL (1) nu pot recunoaște toate limbile fără context. Limbile LL (1) sunt un subset adecvat al limbilor LR (1), care la rândul lor sunt un subset adecvat al tuturor limbilor fără context. Pentru ca o gramatică fără context să fie o gramatică LL (1), nu trebuie să apară anumite conflicte, pe care le descriem în această secțiune.

Terminologie

Fie A un non-terminal. PRIMA ( A ) este (definit a fi) setul de terminale care pot apărea în prima poziție a oricărui șir derivat de la A . URMAȚI ( A ) este uniunea de peste:

FIRST ( B ) unde B este orice non-terminal care urmează imediat A în partea dreaptă a unei reguli de producție .
URMAȚI ( B ) unde B este orice cap al unei reguli de forma B → wA .

LL (1) conflicte

Există două tipuri principale de conflicte LL (1):

PRIM / PRIM conflict

PRIMUL set de două reguli gramaticale diferite pentru aceeași intersecție non-terminală. Un exemplu de conflict LL (1) PRIM / PRIM:

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

PRIMUL ( E ) = { b , ε} și PRIMUL ( E a ) = { b , a }, astfel încât atunci când tabela este tras, există un conflict sub terminalul b regulii producției S .

Caz special: recursivitate stângă

Recursivitatea la stânga va provoca un PRIM / PRIM conflict pe toate alternativele.

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

PRIM / URMARE conflict

PRIMUL și URMĂRITUL set de reguli gramaticale se suprapun. Cu un șir gol (ε) în primul set, nu se știe ce alternativă să selectăm. Un exemplu de conflict LL (1):

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

PRIMUL set de A este acum { a , ε} și următorul set { a }.

Soluții la conflictele LL (1)

Factoring la stânga

Un factor stâng comun este „luat în calcul”.

A -> X | X Y Z

devine

A -> X B
B -> Y Z | ε

Poate fi aplicat atunci când două alternative încep cu același simbol ca un conflict PRIM / PRIM.

Un alt exemplu (mai complex) folosind mai sus FIRST / FIRST exemplu de conflict:

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

devine (fuzionând într-un singur non-terminal)

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

apoi prin factorul de stânga, devine

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

Substituţie

Înlocuirea unei reguli cu o altă regulă pentru a elimina conflictele indirecte sau PRIMUL / URMĂRIRE. Rețineți că acest lucru poate provoca un PRIM / PRIM conflict.

Eliminarea recursivității la stânga

Vedea.

Pentru o metodă generală, consultați eliminarea recursivității la stânga . Un exemplu simplu pentru eliminarea recursivității la stânga: Următoarea regulă de producție a lăsat recursivitatea la E

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

Această regulă nu este altceva decât o listă de Ts separate prin „+”. Într-o formă de expresie regulată T ('+' T) *. Deci regula ar putea fi rescrisă ca

E -> T Z
Z -> '+' T Z
Z -> ε

Acum nu mai există recursivitate și niciun conflict asupra uneia dintre reguli.

Cu toate acestea, nu toate gramaticile fără context au o gramatică LL (k) echivalentă, de exemplu:

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

Se poate arăta că nu există nicio gramatică LL (k) care să accepte limba generată de această gramatică.

Vezi si

Note

^ Rosenkrantz, DJ; Stearns, RE (1970). "Proprietățile gramaticilor deterministe de sus în jos" . Informații și control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 .
^ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). „LL-Gramatici obișnuite”. Instytutu Maszyn Matematycznych : 107–119.
^ Jarzabek, Stanislav; Krawczyk, Tomasz (noiembrie 1975). „LL-Gramatici obișnuite” . Scrisori de prelucrare a informațiilor . 4 (2): 31–37. doi : 10.1016 / 0020-0190 (75) 90009-5 .
^ David A. Poplawski (august 1977). Proprietățile LL-Limbi regulate (Raport tehnic). Universitatea Purdue , Departamentul de Informatică.
^ Parr, Terence și Fisher, Kathleen (2011). „LL (*) fundamentul generatorului de analizor ANTLR”. Notificări ACM SIGPLAN . 46 (6): 425-436. doi : 10.1145 / 1993316.1993548 .CS1 maint: nume multiple: lista autorilor ( link )
^ Belcak, Peter (2020). „Strategia de analiză LL (finită) pentru analiza optimă LL (k)”. arXiv : 2010.07874 [ cs.PL ].
^ Ford, Bryan (2004). „Analizarea gramaticilor de expresie: o bază sintactică bazată pe recunoaștere”. Notificări ACM SIGPLAN . doi : 10.1145 / 982962.964011 .
^ Pat Terry (2005). Compilarea cu C # și Java . Pearson Education. pp. 159–164. ISBN 9780321263605.
^ William M. Waite și Gerhard Goos (1984). Construcția compilatorului . Texte și monografii în informatică. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aici: Sect. 5.3.2, p. 121-127; în special, p. 123.
^ Richard E. Stearns și PM Lewis (1969). "Gramaticile de proprietate și mașinile de masă" . Informații și control . 14 (6): 524-549. doi : 10.1016 / S0019-9958 (69) 90312-X .
^ "Gramaticile LL" (PDF) . Arhivat (PDF) din original la 18.06.2010 . Adus 11.05.2010 .
^ Modern Compiler Design , Grune, Bal, Jacobs și Langendoen

linkuri externe

Un tutorial despre implementarea analizelor LL (1) în C # (arhivat)
Simulator de analiză Acest simulator este utilizat pentru a genera tabele de analiză LL (1) și pentru a rezolva exercițiile cărții.
LL (1) Parser DSL PEG (cadru de instrumente)
Compararea teoretică a limbajului gramaticilor LL și LR
LL (k) Teoria analizei

[1] Rosenkrantz, DJ; Stearns, RE (1970). "Proprietățile gramaticilor deterministe de sus în jos" . Informații și control . 17 (3): 226–256. doi : 10.1016 / s0019-9958 (70) 90446-8 .

[2] Jarzabek, Stanislav; Krawczyk, Tomasz (1974). „LL-Gramatici obișnuite”. Instytutu Maszyn Matematycznych : 107–119.

[3] Jarzabek, Stanislav; Krawczyk, Tomasz (noiembrie 1975). „LL-Gramatici obișnuite” . Scrisori de prelucrare a informațiilor . 4 (2): 31–37. doi : 10.1016 / 0020-0190 (75) 90009-5 .

[4] David A. Poplawski (august 1977). Proprietățile LL-Limbi regulate (Raport tehnic). Universitatea Purdue , Departamentul de Informatică.

[5] Parr, Terence și Fisher, Kathleen (2011). „LL (*) fundamentul generatorului de analizor ANTLR”. Notificări ACM SIGPLAN . 46 (6): 425-436. doi : 10.1145 / 1993316.1993548 .CS1 maint: nume multiple: lista autorilor ( link )

[6] Belcak, Peter (2020). „Strategia de analiză LL (finită) pentru analiza optimă LL (k)”. arXiv : 2010.07874 [ cs.PL ].

[7] Ford, Bryan (2004). „Analizarea gramaticilor de expresie: o bază sintactică bazată pe recunoaștere”. Notificări ACM SIGPLAN . doi : 10.1145 / 982962.964011 .

[8] Pat Terry (2005). Compilarea cu C # și Java . Pearson Education. pp. 159–164. ISBN 9780321263605.

[9] William M. Waite și Gerhard Goos (1984). Construcția compilatorului . Texte și monografii în informatică. Heidelberg: Springer. ISBN 978-3-540-90821-0.Aici: Sect. 5.3.2, p. 121-127; în special, p. 123.

[10] Richard E. Stearns și PM Lewis (1969). "Gramaticile de proprietate și mașinile de masă" . Informații și control . 14 (6): 524-549. doi : 10.1016 / S0019-9958 (69) 90312-X .

[11] "Gramaticile LL" (PDF) . Arhivat (PDF) din original la 18.06.2010 . Adus 11.05.2010 .

[12] Modern Compiler Design , Grune, Bal, Jacobs și Langendoen

Languages

In other projects