Analisi lessicale senza espressioni regolari

Prima di tutto, ci sono state librerie di espressioni regolari per C da prima che venissero inventate le lingue "di livello superiore". Detto solo, i programmi C non sono così snodati come pensano alcune persone.

Per la maggior parte delle grammatiche, il lexing è una questione di ricerca di spazi bianchi e di pochi altri caratteri come () [] {}; per dividere le parole e quindi confrontarle con un elenco di parole chiave per verificare se corrispondono.

Potresti essere interessato ai "parser senza scanner", che non hanno una fase di tokenizzazione separata. Una spiegazione dei vantaggi dei parser senza scanner è fornita all'inizio di questo documento: Filtri disambiguazione per Analizzatori LR generalizzati senza scanner . (Ci sono anche degli svantaggi.)

(I PEG, che sono stati menzionati in altre risposte, possono anche essere usati per costruire parser senza scanner.)

Non c'è nulla di specifico sulle espressioni regolari. Sono semplicemente una scorciatoia che ti permette di generare il codice molto più facilmente e le implementazioni sono comunemente spedite. Tuttavia, fondamentalmente, i lexer sono FSM e le espressioni regolari sono solo un modo per raggiungere questo obiettivo.

Ovviamente puoi usare altri parser, dato che ogni lingua normale è anche libera dal contesto. La domanda riguarda davvero il perché vorresti.

Non c'è nulla di più semplice delle espressioni regolari (come puoi migliorare O (N)?) e cercare di semplificare non aiuta. Puoi sempre usare il backtracking semplice come ha fatto notare Jetti, anche se ti consiglio di evitarlo se possibile.

Se hai intenzione di utilizzare un parser più avanzato per il lexing, probabilmente non avrai affatto bisogno di una fase di lexing. In effetti, i motivi per cui abbiamo una fase di lexing è che è più veloce analizzare i token lessati piuttosto che analizzare i caratteri, insieme a semplificare drasticamente il nostro passo di analisi. Quindi, usando un parser più avanzato, semplicemente perdi tutti i benefici del lexing, in primo luogo.

Ha senso fare un'analisi lessicale con espressioni regolari, o saltare questo passaggio e fare un parsing lessless molto più flessibile e potente con PEG o GLR.