btyacc - Online nel cloud

PROGRAMMA:

NOME

btyacc: an LALR(1) generatore di parser con supporto per il backtracking

SINOSSI

btyacc [-B prefisso] [-d] [-dNOME ...] [-E] [-l] [-r] [-S x.ske] [-tv]
nomefile.y

Descrizione

btyacc è una versione modificata di byacc (Berkeley YACC), che a sua volta è di dominio pubblico
versione del generatore di parser AT&T YACC originale.

btyacc legge le specifiche grammaticali nel file nomefile.y e genera an LR(1)
analizzatore per esso. Il parser è costituito da un insieme di LALR(1) analisi di tabelle e routine del driver
scritto nel linguaggio di programmazione C. btyacc normalmente scrive le tabelle di analisi e il
routine del driver nel file prefisso.tab.c, Dove prefisso il valore predefinito è "y".

Per una descrizione dettagliata del formato di una specifica grammaticale e un eccellente
tutorial su come utilizzare strumenti simili a YACC, vedere il manuale informativo per GNU bisonte. btyacc-
estensioni specifiche sono spiegate di seguito.

Nota: Lo scheletro del parser fornito dall'autore upstream di btyacc compila solo come C++. Utilizzo
lo scheletro /usr/doc/btyacc/examples/btyacc-c.ske per generare un parser che compila entrambi
come C e C++. (Sfortunatamente, questo scheletro alternativo attualmente non controlla malloc()
restituire valori.)

Opzioni

-b prefisso Cambia il prefisso anteposto ai nomi dei file di output nella stringa indicata da
prefisso. Il prefisso predefinito è il carattere "y".

-d Crea un file di intestazione chiamato prefisso.tab.h con prefisso.tab.c,
contenente le definizioni dei simboli e una dichiarazione per YYSTYPE ed yylval.

-DNOME Definire la variabile del preprocessore btyacc NOME, da utilizzare con %ifdef NOME
direttive nel file di grammatica.

-E Stampa la grammatica preelaborata sullo standard output.

-l Non inserire #linea direttive nel codice del parser generato.

-r Scrive il codice del parser e le tabelle associate in file diversi. Mentre il
le tabelle possono essere trovate in prefisso.tab.c come prima, il codice ora viene scritto
a prefisso.codice.c.

-S x.ske Seleziona uno scheletro di parser diverso. Lo scheletro predefinito è cablato nel
programma, ma è possibile trovarne una copia nel file btyaccpa.ske.

-t Fa sì che il codice di debug venga compilato nel parser generato.

-v Scrivere una descrizione leggibile dall'uomo del parser generato in y.uscita. Questo
include stati del parser, azioni per un token look-ahead e informazioni su qualsiasi
conflitti.

BTYACC estensioni

backtracking supporto
Ogni volta che un parser generato da btyacc si imbatte in un errore shift-reduce o reduce-reduce nel
parse table, ricorda il punto di analisi corrente (stack e stato del flusso di input) e va
in modalità di analisi di prova. Quindi continua l'analisi, ignorando la maggior parte delle azioni delle regole. Se funziona
in un errore (attraverso la tabella di analisi o tramite una chiamata di azione YYERRORE), è
torna indietro al punto di conflitto più recente e cerca un'alternativa diversa. se è
trova un percorso di successo (raggiunge la fine dell'input o un invito all'azione YYVALIDO), è
torna indietro fino al punto in cui è entrato per la prima volta in modalità di analisi di prova e continua con un pieno
parse (eseguendo tutte le azioni), seguendo il percorso della prova riuscita.

Le azioni in btyacc sono disponibili in due versioni: {} azioni, che vengono eseguite solo quando non in
modalità di prova, e [] azioni, che vengono eseguite indipendentemente dalla modalità.

Esempio: nelle grammatiche YACC per il C, un hack standard noto come "lexer feedback hack" è
usato per trovare i nomi typedef. Il lexer usa le informazioni semantiche per decidere se un dato
identificatore è un nome typedef o meno e restituisce un token speciale. Con btyacc, no
più bisogno di farlo; il lexer dovrebbe sempre restituire un identificatore. il btyacc
la grammatica ha quindi bisogno di una regola della forma:

nometipo: ID [ if (!IsTypeName(LookupId($1))) YYERRORE; ]

Tuttavia, tieni presente che l'aggiunta di regole di backtracking rallenta il parser. In pratica, tu
dovrebbe cercare di limitare il numero di conflitti nella grammatica a ciò che è assolutamente
necessario. Considera l'utilizzo del "lexer feedback hack" se è una soluzione pulita e
riservare il backtracking per alcuni casi speciali.

btyacc esegue le sue prove usando la regola "prova prima a cambiare, poi prova a ridurre nell'ordine
che le regole in conflitto appaiano nel file di input". Ciò significa che puoi implementare
regole di disambiguazione semantica come, ad esempio: (1) Se sembra una dichiarazione lo è,
altrimenti (2) Se sembra un'espressione lo è, altrimenti (3) è un errore di sintassi
[Ellis & Stroustrup, Annotato C++ Reference Manual, p93]. Per raggiungere questo obiettivo, metti tutto il
regole per le dichiarazioni prima delle regole per le espressioni nel file di grammatica.

Il backtracking viene attivato solo quando l'analisi colpisce uno spostamento/riduzione o una riduzione/riduzione
conflitto in tabella. Se non hai conflitti nella tua grammatica, non ci sono costi aggiuntivi,
altro che qualche codice extra che non verrà mai invocato.

Attualmente, il parser generato esegue no potatura di percorsi di analisi alternativi. Evitare
un'esplosione esponenziale di possibili percorsi (e tempo di analisi), è necessario dire manualmente
il parser quando può buttare via i percorsi salvati usando il YYVALIDO dichiarazione. In
pratica, questo risulta essere abbastanza facile da fare. Ad esempio, un parser C++ può semplicemente
contenere [AAVALID;] dopo ogni dichiarazione completa e regola di dichiarazione, con conseguente
stato di backtracking eliminato dopo aver visto un `;' o `}' - non ci sarà mai un
situazione in cui è utile tornare indietro a uno di questi due.

Servizio token posizione manipolazione
I compilatori spesso hanno bisogno di costruire AST (alberi di sintassi astratti) in modo tale che ogni nodo in un albero
può riguardare l'origine del programma analizzato da cui proviene. Il YYPOSN meccanismo supportato
di btyacc ti aiuta ad automatizzare il calcolo della posizione del testo e ad assegnare il
posizioni di testo calcolate ai nodi AST.

Negli YACC standard ogni token e ogni non terminale ha un YYSTYPE valore semantico
attaccato ad esso. Con btyacc, ogni token e ogni non terminale ha anche un YYPOSN testo
posizione ad esso collegata. YYPOSN è un tipo definito dall'utente.

btyacc mantiene uno stack di valori di posizione del testo nello stesso modo in cui mantiene uno stack
di valori semantici. Per utilizzare la funzione di posizione del testo, è necessario #define , il
seguenti:

YYPOSN Simbolo del preprocessore per il tipo C/C++ della posizione di testo collegata a ogni
token e non terminale.

yyposn Variabile globale di tipo YYPOSN. Il lexer deve assegnare la posizione del testo del
token restituito a yyposn, proprio come assegna il valore semantico di
restituito token a yylval.

YYREDUCEPOSNFUNC
Simbolo del preprocessore per una funzione che viene chiamata immediatamente dopo il normale
è stata eseguita la riduzione delle regole grammaticali, per ridurre le posizioni del testo situate su
la pila.

In genere, questa funzione estrae le posizioni del testo dalla regola del lato destro
componenti e li assegna alla struttura/albero $$ restituito o, se no
Viene restituito il valore $$, li mette nella posizione del testo ret dove sarà
ripreso da altre regole in seguito. Il suo prototipo è:

nulla RiduciPosn(
YYPOSN& macerare,
YYPOSN* termine_posns,
YYSTYPE* term_vals,
int termine_n,
int stk_pos,
int ahicar,
YYPOSN& sìposn,
Tipologia di utente extra);

ret Riferimento alla posizione del testo restituita dalla regola. Devi sovrascrivere
questo con la posizione del testo calcolato che la regola produce, analogamente a
il valore semantico $$.

termine_posns
Matrice dei componenti della regola del lato destro' YYPOSN posizioni del testo,
analogo a $1, $2, ..., $N per i valori semantici.

term_vals Array dei componenti della regola sul lato destro' YYSTYPE valori. Questi sono
i $1, ..., $N stessi.

term_no Numero di componenti nella parte destra della regola ridotta, ovvero il
dimensione degli array term_posns e term_vals. Uguale anche a N in $1, ...,
$ N.

stk_pos YYSTYPE/YYPOSN posizione dello stack prima della riduzione.

yychar Gettone Lookahead che segue immediatamente il lato destro ridotto
componenti.

sìposn YYPOSN del gettone che segue immediatamente il lato destro ridotto
componenti.

extra Argomento extra definito dall'utente passato a ReducePosn.

YYREDUCEPOSNFUNCARG
Argomento aggiuntivo passato alla funzione ReducePosn. Questo argomento può essere qualsiasi
variabile definita in btyaccpa.ske.

Token deallocazione durante errore recupero
Per la maggior parte dei generatori di parser simili a YACC, l'azione del parser generato all'incontro
un errore di analisi consiste nell'eliminare i valori semantici e i token di input fino a quando una regola contenente
lo speciale non terminale errore può essere abbinato. L'eliminazione dei token viene eseguita semplicemente da
sovrascrivere variabili e voci di array di tipo YYSTYPE con nuovi valori.

Sfortunatamente, questo approccio porta a una perdita di memoria se YYSTYPE è un tipo di puntatore. btyacc
consente di fornire funzioni per ripulire i valori semantici e di posizione del testo, tramite
#definei seguenti simboli nel preambolo del file di grammatica:

YYDELETEVAL
Simbolo del preprocessore per una funzione da chiamare prima del valore semantico di un token
o non terminale viene scartato.

YYDELETEPOSN
Simbolo del preprocessore per una funzione da chiamare prima della posizione del testo di un token
o non terminale viene scartato.

Entrambe le funzioni vengono chiamate con due argomenti. Il primo argomento di tipo YYSTYPE or YYPOSN
è il valore che verrà scartato. Il secondo argomento è di tipo int ed è uno di
tre valori:

0 scartare il token di input

1 stato di scarto in pila

2 ripulire lo stack durante l'interruzione

Dettagliato sintassi errore segnalazione
Se hai #define la variabile del preprocessore YERRORE_DETTAGLIATO nel tuo file di grammatica, devi
definire anche la seguente funzione di elaborazione degli errori:

nulla yyerror_dettagliato(
carattere* testo,
int sbagliare,
YYSTYPE&
ert_value,
YYPOSN& ert_posn);

messaggio di errore di testo

codice di errore del token che ha causato l'errore

ert_value
valore del token che ha causato l'errore

errt_posn posizione del testo del token che ha causato l'errore

preprocessore direttive
btyacc supporta la definizione di simboli e l'azione su di essi con direttive condizionali all'interno
file di grammatica, non diversamente dal preprocessore C.

%definire NOME
Definire il simbolo del preprocessore NOME. Equivalente all'opzione della riga di comando
-DNOME.

%ifdef NOME
Se variabile del preprocessore NOME è definito, elabora il testo da questo %ifdef a
La chiusura %finisci se, altrimenti saltalo.

%endif Direttiva di chiusura per %ifdef. %ifdefs non possono essere nidificati.

%includere NOME DEL FILE
Elabora il contenuto del file denominato NOME DEL FILE. Un solo livello di nidificazione di %includere
È permesso.

%ident STRING
Inserisci un `#identificazione STRING' direttiva nel file di output. STRING deve essere un
costante stringa racchiusa tra "".

Ereditato gli attributi
Gli attributi ereditati non sono documentati. (Vedi il README e il codice sorgente btyacc per a
poche informazioni.) Se capisci come funzionano, contattami a[email protected]>!

Bugs

La complessità dell'analisi nel caso peggiore è esponenziale per qualsiasi grammatica che consente
backtracking che abbia luogo. In altre parole, un parser generato da btyacc costituisce a
denial-of-service se utilizzato in applicazioni in cui un utente malintenzionato è in grado di fornire
dati appositamente predisposti come input per il parser. (Per tutti i dati di input "normali", il
la complessità potenzialmente esponenziale non è normalmente un problema.)

di bisonte %aspettarsi direttiva non è supportata.

Non c'è %altro ed %ifnd. %ifdefs e %includeres non possono essere nidificati.

Autori

Robert Corbetta[email protected]> /[email protected]> era uno dei
autori originali di Berkeley byacc. Chris Dodd[email protected]> avuto il brillante
idea di aggiungere capacità di backtracking ed è responsabile del backtracking iniziale
i cambiamenti. Vadim Maslov[email protected]> migliorato ulteriormente il codice.

Questa documentazione è stata scritta da Richard Atterer[email protected]> per Debian
distribuzione GNU/Linux, ma è donata al pubblico dominio e può quindi essere utilizzata liberamente
per qualsiasi scopo.

File

/usr/doc/btyacc/examples/btyaccpa.ske

/usr/doc/btyacc/examples/btyacc-c.ske

/usr/doc/btyacc/LEGGIMI

See anche

bisonte(1) (o "info bisonte"), peracc(1), sì, sì(1), antler(1)

btyacc(1)

Usa btyacc online utilizzando i servizi onworks.net