Ich habe eine Prüfung der Praxis für meinen Compiler natürlich mit den folgenden Fragen, die ich nicht bekommen kann:Warum können wir eine CFG nicht zum Scannen/Tokenisieren verwenden?
Hat jemand irgendwelche Ideen?
Diese beiden Aussagen sind falsch.
Sie können ein CFG absolut zum Scannen und Tokenization verwenden. Tatsächlich ist jede reguläre Sprache auch kontextfrei, sodass Sie Ihren Scanner so umschreiben können, dass er eine kontextfreie Grammatik anstelle eines regulären Ausdrucks scannt. Der Hauptgrund dafür ist, dass es normalerweise übertrieben ist. Token haben selten eine komplexe Struktur und ein regulärer Ausdruck funktioniert normalerweise gut. Sie können sich jedoch Fälle vorstellen, in denen Sie eine CFG verwenden möchten. Zum Beispiel erfordert in C++ die Behandlung von engen Winkelstreben in Schablonen oft eine spezielle Umhüllung durch den Compiler. Zum Beispiel sollte vector<vector<int>> tokenize als vector<vector<int>>, obwohl ein Standardsatz von regulären Ausdrücken die beiden Schließ Klammern als >> Token gescannt werden würde. Durch Verwendung einer kontextfreien Grammatik zum Scannen könnte dies durch mehr Kontext verringert werden.
Sie können auch unbedingt reguläre Ausdrücke zum Parsen verwenden, sofern Ihre Sprache ausreichend einfach ist. Die meisten Sprachen sind zu komplex, um mit einem regulären Ausdruck codiert zu werden (z. B. kann alles, was verschachtelte Klammern enthält, nicht mit regulären Ausdrücken analysiert werden). Daher verwenden wir häufig CFGs, aber es gibt Sprachen, die mit regulären Ausdrücken analysiert werden können. Zum Beispiel eine Beschreibung eines DFA als Tabelle wie diese auf jeden Fall durch einen regulären Ausdruck analysiert werden kann:
0 1
q0 q1 q0
q1 q0 q1
Die meisten realen Programmiersprachen keine regelmäßige Struktur haben, aber, und so in der Praxis kontext- stattdessen werden freie Grammatiken verwendet.
Hoffe, das hilft!
Eigentlich sollte ein CFG ausreichend mächtig sein, um Token zu beschreiben, aber es wäre ein PITA und Overkill. Aber ich bin wahrscheinlich pingelig. – delnan
Wenn Sie einen tabellenbasierten Bottom-Up-Parser verwendet haben, ist die Parse-Tabelle viel größer als eine FSM-Übergangstabelle. – blackcompe