Nez is a PEG(Parsing Expressing Grammar)-based open grammar language that allows us to describe complex syntax constructs without action code. Since open grammars are declarative and free from a host programming language of parsers, software engineering tools and other parser applications can reuse once-defined grammars across programming languages. A key challenge to achieve practical open grammars is the expressiveness of syntax constructs and the resulting parser performance, as the traditional action code approach has provided very pragmatic solutions to these two issues. In Nez, we extend the symbol-based state management to recognize context-sensitive language syntax, which often appears in major programming languages. In addition, the Abstract Syntax Tree constructor allows us to make flexible tree structures, including the left-associative pair of trees. Due to these extensions, we have demonstrated that Nez can parse not all but many grammars. Nez can generate various types of parsers since all Nez operations are independent of a specific parser language. To highlight this feature, we have implemented Nez with dynamic parsing, which allows users to integrate a Nez parser as a parser library that loads a grammar at runtime. To achieve its practical performance, Nez operators are assembled into low-level virtual machine instructions, including automated state modifications when backtracking, transactional controls of AST construction, and efficient memoization in packrat parsing. We demonstrate that Nez dynamic parsers achieve very competitive performance compared to existing efficient parser generators.
Data-dependent grammars @cite_19 @cite_3 share similar ideas in terms of recognizing context-sensitive syntax. Briefly, these grammars uses a variable to be bound to a parsed result, which seems to be the addition of symbols in Nez. Data-dependent grammars are more expressive in a way that they express more complex condition such as |([n>0] OCTET n:=n−1 )|, while Nez is more declarative and leads to better readability. In addition, the better expressiveness of data-dependent grammars suggests a future promising extension of Nez, including numerical values in the symbol table.
@cite_19 @cite_3
1560736395 2112874453 1986318362 1964494435
Dependent grammars extend context-free grammars by allowing semantic values to be bound to variables and used to constrain parsing. Dependent grammars can cleanly specify common features that cannot be handled by context-free grammars, such as length fields in data formats and significant indentation in programming languages. Few parser generators support dependent parsing, however. To address this shortcoming, we have developed a new method for implementing dependent parsers by extending existing parsing algorithms. Our method proposes a point-free language of dependent grammars, which we believe closely corresponds to existing context-free parsing algorithms, and gives a novel transformation from conventional dependent grammars to point-free ones. To validate our technique, we have specified the semantics of both source and target dependent grammar languages, and proven our transformation sound and complete with respect to those semantics. Furthermore, we have empirically validated the suitability of our point-free language by adapting four parsing engines to support it: an Earley parsing engine; a GLR parsing engine; memoizing, arrow-style parser combinators; and PEG parser combinators. Standard statistical language models use n-grams to capture local dependencies, or use dynamic modeling techniques to track dependencies within an article. In this paper, we investigate a new statistical language model that captures topic-related dependencies of words within and across sentences. First, we develop a topic-dependent, sentence-level mixture language model which takes advantage of the topic constraints in a sentence or article. Second, we introduce topic-dependent dynamic adaptation techniques in the framework of the mixture model, using n-gram caches and content word unigram caches. Experiments with the static (or unadapted) mixture model on the North American Business (NAB) task show a 21 reduction in perplexity and a 3-4 improvement in recognition accuracy over a general n-gram model, giving a larger gain than that obtained with supervised dynamic cache modeling. Further experiments on the Switchboard corpus also showed a small improvement in performance with the sentence-level mixture model. Cache modeling techniques introduced in the mixture framework contributed a further 14 reduction in perplexity and a small improvement in recognition accuracy on the NAB task for both supervised and unsupervised adaptation. The addition of preferences to normal logic programs is a convenient way to represent many aspects of default reasoning. If the derivation of an atom A1 is preferred to that of an atom A2, a preference rule can be defined so that A2 is derived only if A1 is not. Although such situations can be modelled directly using default negation, it is often easier to define preference rules than it is to add negation to the bodies of rules. As first noted by [Proc. Internat. Conf. on Logic Programming, 1995, pp. 731-746], for certain grammars, it may be easier to disambiguate parses using preferences than by enforcing disambiguation in the grammar rules themselves. In this paper we define a general fixed-point semantics for preference logic programs based on an embedding into the well-founded semantics, and discuss its features and relation to previous preference logic semantics. We then study how preference logic grammars are used in data standardization, the commercially important process of extracting useful information from poorly structured textual data. This process includes correcting misspellings and truncations that occur in data, extraction of relevant information via parsing, and correcting inconsistencies in the extracted information. The declarativity of Prolog offers natural advantages for data standardization, and a commercial standardizer has been implemented using Prolog. However, we show that the use of preference logic grammars allow construction of a much more powerful and declarative commercial standardizer, and discuss in detail how the use of the non-monotonic construct of preferences leads to improved commercial software. We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular, our new parsing engine handles (1) full scannerless context-free grammars with (2) regular expressions as right-hand sides for defining nonterminals. YAKKER also includes (3) facilities for binding variables to intermediate parse results and (4) using such bindings within arbitrary constraints to control parsing. These facilities allow the kind of data-dependent parsing commonly needed in systems applications, particularly those that operate over binary data. In addition, (5) nonterminals may be parameterized by arbitrary values, which gives the system good modularity and abstraction properties in the presence of data-dependent parsing. Finally, (6) legacy parsing libraries,such as sophisticated libraries for dates and times, may be directly incorporated into parser specifications. We illustrate the importance and utility of this rich collection of features by presenting its use on examples ranging from difficult programming language grammars to web server logs to binary data specification. We also show that our grammars have important compositionality properties and explain why such properties areimportant in modern applications such as automatic grammar induction. In terms of technical contributions, we provide a traditional high-level semantics for our new grammar formalization and show how to compile grammars into non deterministic automata. These automata are stack-based, somewhat like conventional push-down automata,but are also equipped with environments to track data-dependent parsing state. We prove the correctness of our translation of data-dependent grammars into these new automata and then show how to implement the automata efficiently using a variation of Earley's parsing algorithm.