Embedding semantics in LR parser tables

This paper addresses two of the problems commonly associated with LR parsing and syntax directed translation schemes, namely grammar stratification and excessively large table size, A solution is discussed which can eliminate stratification of the grammar by allowing the designer to embed semantics directly within the LR table (i.e., at shift and error entries instead of just at reduce entries) and to use global context to determine what semantics should be performed. The non-stratified grammar can produce a significantly smaller LR table than the corresponding stratified grammar. The compatibility of this scheme with commonly used table compaction techniques is also discussed.     

An LR parsing technique for extended context-free grammars

Extended context-free grammars allow regular expressions to appear in productions right hand sides, and are a clear and natural way to describe the syntax of programming languages.In this paper an LR parsing technique for extended context-free grammars is presented, which is based on an underlying transformation of the grammar into an equivalent context-free one.The technique is suitable for inclusion in one-pass compilers: the implementation requires little extensions to the algorithms working for normal LR grammars. Besides describing the parsing method, the paper shows also the algorithms for deriving the parsing tables; tables optimization is also discussed. Finally, this technique is compared with other proposals appeared in the literature.     

LR分析的教学法探讨

LR分析法是编译程序语法分析中最常用且有效的自下而上的分析方法,理论较完善,适用于大多数上下文无关语言的分析。本文主要探讨LR分析的教学方法,采用"启发+关联式"教学法,引导学生理解LR分析的内涵。     

基于藏语语义分析的机器翻译技术研究

藏汉机器翻译技术跟汉英机器翻译技术有所不同,其中,很重要的一个方面,藏语更依赖于格助词等虚词在句子中的作用,格助词种类繁多,用法差异很大。针对藏语格助词进行分析,在藏语短语句法树库的基础上,加入了藏语本体特征的语义信息,形成融合藏语语义信息的藏汉机器翻译方法。通过对比基于短语和句法的实验分析,该方法可以很好地应用于藏汉机器翻译系统。     

On a method for optimizing LR parsers

It is shown that if the basic method for eliminating single productions from canonical LR parsers developed by Pager is applied to an SLR parser and the resulting parser is free of conflicts, then the resulting parser is a valid parser which accepts exactly the strings in the language. However, if the elimination process is performed during the construction of an SLR parser, then the resulting parser may be invalid even if it were free of conflicts.     

Error handling in a parallel LR substring parser

Parallel parsing is currently receiving attention but there is little discussion about the adaptation of sequential error handling techniques to these parallel algorithms. We describe a noncorrecting error handler implemented with a parallel LR substring parser. The parser used is a parallel version of Cormack's LR substring parser. The applicability of noncorrecting error handling for parallel parsing is discussed. The error information provided for a standard set of 118 erroneous Pascal programs is analysed. The programs are run on the sequential LR substring parser.     

编译原理中的LR类分析方法的教学研究

编译原理课程的教学不仅要介绍编译的基本原理和技术,还要培养学生的学习兴趣、专业思维和科学研究的方法及能力,文章以LR类分析方法为例,以还原知识的发现过程为主线,重现解决问题的思路与方法,以期培养学生的专业学习兴趣和科研能力。     

基于最大熵方法汉语基本短语分析

提出了一个汉语基本短语分析模型,将汉语短语的边界划分和短语标识分开,假定这两个过程相互独立,采用最大熵方法分别建立模型解决。最大熵模型的关键是如何选取有效的特征,文中给出了两个步骤相关的特征空间以及特征选择过程和算法。实验表明,模型的短语定界精确率达到95.27％,标注精确率达到96.2％。     

Defining,analysing and implementing communication protocols using attribute grammars

A new approach to describing communication protocols is introduced. In the style of a formal language, the protocol is considered as the set of all legal sequences of symbols that can be exchanged by the communicating processes. Although context free grammars cannot adequately describe such sequences, it is shown that attribute grammars may be used. Examples are given which show that common protocol features such as interleaving, windowing and flow control can be described by attribute grammars.It is shown how deadlock-proneness of a protocol can be formalised as a property of its attribute grammar specification, and the undecidability of deadlock-proneness for arbitrary grammars is proved. An algorithm is given for determining whether a protocol is deadlock-prone in the decidable case.A method of automatically implementing protocols from their specifications is described. The implementation takes the form of a pair of communicating attributed pushdown automata. These are based on LR(0) parsers, with attribute evaluation being performed in parallel with the parse; attribute values are used to help direct the parse. Consideration is also given to the handling of errors.     

基于统计的句法分析方法研究

在概述统计句法分析主要特征的基础上,对目前主流分析方法进行了深入分析,提出了实用化的基于统计的句法分析器必须引入结构信息、上下文信息、词汇信息以及语义信息才能提高性能和可靠性的观点。总结了基于统计的汉语句法分析方法当前的研究现状,最后探讨了基于统计的汉语句法分析方法的不足之处和发展趋势。     

Precedence parsing using domolki's algorithm

A parsing Algorithm for the class of precedence grammars is described, using Domolki's algorithm. The main strategy of the algorithm is that with the detection of the right‐end of the handle of a right sentential form, the determination of the production rule necessary for reducing the string (thus the handle) is complete.     

E-parser: An implementation of a deterministic GB-related parsing system

This paper describes an implementation of a deterministic parsing system, described in Nordgård (1993). The syntax of heuristic rules and how the rules interact with the basic operations of the parser constitute the bulk of the article. The implementation is written in Medley Interlisp, and the system can be run on Sun or Xerox workstations. Torbjørn Nordgård is associate professor of computational linguistics in the Department of Linguistics and Phonetics, University of Bergen. His research interests include computational linguistics, theoretical linguistics, in particular formal syntax and semantics, and philosophy of science. He has published A GB-Related Parser for Norwegian(Bern: Peter Lang) and he is one of the authors of Generativ syntaks: Ei innføring via norsk(Oslo: Novus).     

一种LR语法分析中的错误恢复方法

语法分析中的错误恢复是现代编译器中智能感知功能的重要组成部分,错误恢复的效果直接影响到智能感知功能的性能。在分析LR语法分析中LR分析表特性的基础上,提出了一种对LR分析表中的Goto表项进行改造来进行语法错误的诊断和恢复的方法。该方法充分利用了LR分析表中的空闲表项,在不增加空间需求的情况下,提高了语法错误的诊断和恢复的效率和准确率。     

Compact recursive-descent parsing of expressions

Compiler writing tools, such as parser generators, are-commonly used to build new operators. Nevertheless, constructing compilers by hand remains common. Such compilers are often built using recursive-descent parsing for most of the language and operator-precedence parsing for expressions. This paper describes a simple technique for parsing expressions using recursive descent that avoids the usual proliferation of procedures that occurs when recursive descent is used to parse expressions. By taking advantage of the similarity of the productions describing expressions in most languages, the n + 1 procedures usually required to parse expressions with n precedence levels can be replaced with a table and two procedures.     

基于Z规格的LR(k)形式化分析及验证

在编译器的构造中,常由于语义的二义性等问题导致不正确的目标程序.为解决此问题,提出了一种新型的语法及语义正确性验证方案,即建立LR (k)文法和Z规格说明的联系,以此构造LR (k)文法的形式化描述及其形式化验证.实验结果表明,该方案能有效描述并检测LR (k)文法分析器中的语法错误及语义二义性,有助于提高分析器的有效性.     

Incremental generation of LR parsers

Implementation of a new compiler usually requires making frequent adjustments to grammar definitions. An incremental technique for updating the parser tables after a monor change to the grammer could potentially save much computational effort. More importantly, debugging a grammar is made easier if the grammar is re-checked for correctness after each small change to the grammar. The basic design philosophy of an incremental parser generator, and incremental algorithms for LR(0), SLR(1) and LALR(1) parser generation are discussed in this paper. Some of these algorithms have been incorporated into an implementation of an incremental LALR(1) parser generator.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

语法分析方法研究评述及其应用

语法分析作为编译过程中一个不可缺少的步骤,对其进行研究有着非常重要的意义.阐述了语法分析方法研究的现状,并对之进行了具体的分析和探讨,介绍了语法分析方法的各种应用,对语法分析方法进行了总结和展望.