標題: ON THE LOOK-AHEAD PROBLEM IN LEXICAL ANALYSIS
作者: YANG, W
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
公開日期: 1-Aug-1995
摘要: Modern programming languages use regular expressions to define valid tokens, Traditional lexical analyzers based on minimum deterministic finite automata for regular expressions cannot handle the look-ahead problem. The scanner writer needs to explicitly identify the look-ahead states and code the buffering and re-scanning operations by hand. We identify the class of finite look-ahead finite automata, which is general enough to include all finite automata of practical lexical analyzers, Finite look-ahead finite automata are then transformed into suffix finite automata. A new lexical analyzer makes use of the suffix finite automata to identify tokens. The new lexical analyzer solves the look-ahead problem in a table-driven approach and it can detect lexical errors at an earlier time than traditional lexical analyzers. The extra cost of the new lexical analyzers is the larger state transition table and three additional 1-dimensional tables. Incremental lexical analysis is also discussed.
URI: http://dx.doi.org/10.1007/BF01213079
http://hdl.handle.net/11536/1806
ISSN: 0001-5903
DOI: 10.1007/BF01213079
期刊: ACTA INFORMATICA
Volume: 32
Issue: 5
起始頁: 459
結束頁: 476
Appears in Collections:Articles