qual è la differenza tra lex e yacc

Question

Ho lavorato con lex per eseguire del codice ogni volta che viene trovata un'espressione regolare, Can Yacc può fare qualcosa di più? Se sì, allora cosa?

Answer 1

Lex è uno strumento per la costruzione di analizzatori lessicali, che possono eseguire alcune cose lessicali piuttosto stupide (come trovare parole chiave). Yacc è un generatore di parser, che può creare parser per linguaggi realistici. La sua analisi è normalmente basata sull'output di lex (che è un flusso di token) e da questo può creare il tuo parse-tree del linguaggio di programmazione - qualcosa che è più che less.

Tradizionalmente, i compilatori di compilatori distinguono tra analisi lessicale e sintattica - che sono due passaggi importanti in un compilatore (ulteriori da seguire, ad esempio creazione di codice, ottimizzazione).

Answer 2

Sì, YACC è un parser, Lex è un analizzatore lessicale. In genere vengono utilizzati insieme: si specifica la stringa di input e YACC l'input con token fornito da Lex.

Ora, un'espressione regolare può rappresentare solo le lingue regolari. Uno dei limiti di un linguaggio normale è la mancanza di "memoria". Non è possibile definire le regole per l'accettazione più in basso nella stringa in base a ciò che è venuto prima.

Questo è evidente soprattutto nel caso di parentesi. Una lingua normale non può corrispondere alla parentesi annidata al livello corretto. O qualsiasi altra struttura del genere. Le grammatiche dei (più) linguaggi informatici possono e fanno, e, a causa di ciò, non possono essere analizzate con un Lexer o un'espressione regolare. Ecco dove entra YACC.

Si può invertire anche la domanda. Se YACC può fare di più, perché non usarlo per l'analisi lessicale? Bene, succede che tu possa verificare la validità di un'espressione regolare in modo molto efficiente, il che non è il caso delle grammatiche generali - non allo stesso livello. Ancora, YACC può fare analisi lessicali di base, se le regole lessicali del linguaggio sono abbastanza semplici.

Answer 3

lex è un lexical analyzer. Divide il testo in token. La sua potenza è approssimativamente equivalente alla corrispondenza delle espressioni regolari. yacc è un parser generator. Prende una sequenza di token (per esempio da lex) e li interpreta come serie di affermazioni. Il suo potere è approssimativamente equivalente alle grammatiche senza contesto.

Una tipica applicazione di lex e yacc è per l'implementazione dei linguaggi di programmazione. lex ridefinisce l'input, suddividendolo in parole chiave, costanti, punteggiatura, ecc. yacc implementa quindi l'effettivo linguaggio del computer; riconoscere un'istruzione for, ad esempio, o una definizione di funzione.

In senso pratico, si usa spesso lex per elaborare il testo di input in blocchi. Quindi usi yacc per mettere insieme quei pezzi e elaborarli in un significato più ampio.

Answer 4

lex è per l'input di tokenizzazione. Ossia, separando il tuo input negli oggetti di livello più basso che la tua grammatica definisce. Ad esempio, si usa lex per identificare parole chiave, identificatori, stringhe, commenti, spazi bianchi e così via.

yacc è per analizzare la grammatica . Una grammatica è una descrizione della tua lingua, in genere definita in EBNF o qualche altra grammatica senza contesto. Una volta che descrivi la tua grammatica su yacc, puoi usarla per eseguire le azioni del tuo strumento quando vengono riconosciuti elementi della lingua. Ciò potrebbe essere, ad esempio, la costruzione di alberi di sintassi per la risoluzione di espressioni, la definizione di oggetti di ambito, la registrazione di definizioni di variabili e così via.

Sono prodotti gratuiti.

Answer 5

lex e yacc sono normalmente utilizzati insieme. Questo è il modo di solito si costruisce un'applicazione utilizzando sia:

flusso di input (caratteri) -> Lex (gettoni) -> Yacc (Abstract Syntax Albero) -> Il tuo Applcation

Più in generale, cosa Lex farà un file sorgente dall'inizio, e cercherà di abbinare un numero di espressioni regolari (lex ha il suo, una sintassi speciale per questo, che è un po 'diversa dalle espressioni regolari perl o sed), e quindi invocherà un altro programma con ciascun token che riconosce. I token possono essere semplicemente un semplice valore enumerato, come per una parola chiave o un operatore, oppure potrebbero avere dei metadati allegati, come per un valore letterale.

Lex è solitamente (sebbene non necessariamente) utilizzato per invocare Yacc. Yacc usa un algoritmo di parser LALR, che, grosso modo, funziona spingendo ogni token su una pila. Se lo stack ha una sequenza di token che riconosce, scatterà tutti i token, eseguirà un'azione e rimetterà un altro token in pila.

Il vocabolario corretto per ciò che funziona su Yacc è in realtà terminali e non terminali. Un terminale è un token che ha ottenuto dal programma di richiamo (di solito Lex), e un non-terminale è il risultato della corrispondenza di una sequenza sul suo stack.

Generalmente le azioni intraprese da ciascuna regola Yacc sono o per valutare il risultato di un calcolo a cui la regola corrisponde, o per produrre una rappresentazione intermedia, come un albero di sintassi, per un altro livello di applicazione da elaborare.

Yacc, come lex, può essere utilizzato separato dall'altro. Ad esempio, è possibile utilizzare Yacc passandogli singoli caratteri dal testo sorgente e utilizzare le regole Yacc per riconoscere ogni tipo di token. Tuttavia, Yacc non è progettato per essere molto facile da usare in questo modo, e quindi il lexer risultante sarà molto più complesso di un lexer equivalente in Lex. Un uso più tipico sarebbe quello di creare un lexer codificato a mano per motivi di prestazioni o perché è necessario un lexer più intelligente. Un esempio comune del secondo caso è quello usato nei linguaggi C-like che devono conoscere i precedenti usi degli identificatori per sapere se sono usati per descrivere tipi o variabili.