On the applicability of the longest-match rule in lexical analysis

檔案

日期

2002-10-01

類型

期刊名稱

COMPUTER LANGUAGES SYSTEMS & STRUCTURES

卷期與頁次

第 28 卷第 3 期,頁 273–288

ISSN

1477-8424

語言

英文

摘要

The lexical analyzer of a compiler usually adopts the longest-match rule to resolve ambiguities when deciding the next token in the input stream. However, that rule may not be applicable in all situations. Because the longest-match rule is widely used, a language designer or a compiler implementor frequently overlooks the subtle implications of the rule. The consequence is either a flawed language design or a deficient implementation. We propose a method that automatically checks the applicability of the longest-match rule and identifies precisely the situations in which that rule is not applicable. The method is useful to both language designers and compiler implementors. In particular, the method is indispensable to automatic generators of language translation systems since, without the method, the generated lexical analyzers can only blindly apply the longest-match rule and this results in erroneous behaviors. The crux of the method consists of two algorithms: one is to compute the regular set of the sequences of tokens produced by a nondeterministic Mealy automaton when the automaton processes elements of an input regular set. The other is to determine whether a regular set and a context-free language have nontrivial intersection with a set of equations. (C) 2002 Elsevier Science Ltd. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Yang, W., Tsay, C., & Chan, J. (2002). On the applicability of the longest-match rule in lexical analysis. COMPUTER LANGUAGES SYSTEMS & STRUCTURES, 28(3), 273–288. https://doi.org/10.1016/S0096-0551(02)00014-0

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/28507