Grammar Transformers

Notes:

Grammar relations can be employed to define various preservation properties for grammar transformations. Grammar transformations can be modeled as partial functions on grammars, say partial grammar transformers. The Grammar Transformer is responsible for converting the grammar of the target language into grammars that can be used to validate templates as well as the instantiation data. Typical grammar transformations are the elimination of left/ right recursion, and the coding of priority and associativity information in grammar rules. One method uses projections based on general regular tree grammars extended with notions of live and dead, and denies the analysis as mutually recursive grammar transformers. During grammar debugging, only the grammar transformer and the parser generator need to be used, maybe followed by the test program generator.

Pate is a parser for restricted and unrestricted grammars and a grammar transformer from a context-free grammar to Chomsky Normal Form (CNF). The grammar transformer part of Pate is an instructional tool for converting a context-free grammar to Chomsky Normal Form (CNF) through a series of steps. A speech recognition module may consist of three sub-modules, including a command interpreter, a speech recognition engine, and a grammar transformer. A grammar transformer may produce a rule-based specification in Schematron from a grammar-based XML Schema document. To be able to process the grammar programmatically, it is required to transform HTML form of grammar to more suitable representation. To transform the Haskell grammar to the appropriate form, a grammar transformer was created.

Resources:

Wikipedia:

See also:

Natural Language Parsing

Increasing visualization and interaction in the automata theory course [HTML] from duke.edu T Hung… – ACM SIGCSE Bulletin, 2000 – dl.acm.org … In this section we briefly describe the previous version of P&t~, and in the next section describe the new fea- tures added to P~t~. P~t~ is a parser for restricted and unrestricted grammars and a grammar transformer from a context-free grammar to Chomsky Normal Form (CNF). … Cited by 40 – Related articles – BL Direct – All 11 versions

Formal language, grammar and set-constraint-based program analysis by abstract interpretation [PDF] from psu.edu P Cousot… – … of the seventh international conference on …, 1995 – dl.acm.org Page 1. Abstract Formal Language, Grammar and Set-Constraint-Based Program Analysis by Abstract Interpretation Patrick COUSOT LIENS, Ecole Normale Sup&ieure 75230 Paris cedex 05, France cousot~dmi. ens. fr Grammar … Cited by 121 – Related articles – All 10 versions

Grammar adaptation [PDF] from cwi.nl R Lämmel – FME 2001: Formal Methods for Increasing Software …, 2001 – Springer … 3.3 Grammar Transformers The above grammar relations can be employed to define various preservation properties for grammar transformations. We model grammar transformations as partial functions on grammars, say partial grammar transformers. Page 9. 558 R. Lämmel … Cited by 78 – Related articles – BL Direct – All 11 versions

Reading checks with multilayer graph transformer networks [PDF] from uni-hamburg.de Y Le Cun, L Bottou… – Acoustics, Speech, and Signal …, 1997 – ieeexplore.ieee.org … The grammar transformer T,,,, selects the paths of the recognition graph that represent valid character sequences for check amounts. … The output of the grammar transformer, called the interpretation graph, contains all the paths in the recognition graph that … Cited by 25 – Related articles – BL Direct – All 9 versions

Global training of document processing systems using graph transformer networks [PDF] from lecun.org L Bottou, Y Bengio… – Computer Vision and Pattern …, 1997 – ieeexplore.ieee.org … path. This sequence of characters may or may not be a valid check amount. THE GRAMMAR TRANSFORMER T,,,, selects the paths of the recognition graph that represent valid character sequences for check amounts. This … Cited by 27 – Related articles – BL Direct – All 16 versions

An architecture for an xml-template engine enabling safe authoring F Hartmann – … and Expert Systems Applications, 2006. DEXA’ …, 2006 – ieeexplore.ieee.org … Grammar Transformer … D Solution element 2: Grammar Transformer The Grammar Transformer is responsible for converting the grammar of the target language into grammars that can be used to validate templates as well as the instantiation data. … Cited by 9 – Related articles – All 3 versions

A collection of tools for making automata theory and formal languages come alive [PDF] from psu.edu SH Rodger, AO Bilska, KH Leider… – ACM SIGCSE …, 1997 – dl.acm.org … The parse tree for abbcca is shown in Figure 5. 3.3 Pitt5 – Grammar Transformer The grammar transformer part of Pate is an instructional tool for converting a context-free grammar to Chomsky Normal Form (CNF) through a series of steps. … Cited by 44 – Related articles – BL Direct – All 12 versions

Precedence grammar and its transformation G Degui, L Lei… – Software Engineering Research …, 2006 – ieeexplore.ieee.org … the sake of convenient compiler design from these grammars, two algorithms converting precedence grammars to other forms and their correctness discussions are also given in section 3 and section 4. Keywords: Precedence Grammar; Grammar Transformer; Super Grammar; … Cited by 3 – Related articles – All 3 versions

Dependence analysis for recursive data [PDF] from psu.edu YA Liu – Computer Languages, 1998. Proceedings. 1998 …, 1998 – ieeexplore.ieee.org … The method uses projections based on general regular tree grammars extended with notions of live and dead, and denes the analysis as mutually recursive grammar transformers. To guar- antee that the analysis terminates, we use carefully de- signed approximations. … Cited by 22 – Related articles – All 22 versions

Usability and portability of a compiler writing system O Lecarme – Methods of Algorithmic Language Implementation, 1977 – Springer … For example, during grammar debugging, only the grammar transformer and the parser generator need to be used, maybe followed by the test program generator. … Page 21. 81 Figure I – System structure ~en~ egrated cription i grammar transformer scanner generater … Cited by 3 – Related articles – All 3 versions

Activities of interactive speech technology consortium (ISTC) targeting open software development for MMI systems [PS] from tut.ac.jp T Nitta, S Sagayama, Y Yamashita… – Robot and Human …, 2004 – ieeexplore.ieee.org … modules. 2.1 Speech recognition module (SR.M) [lOl,[lll Figure 2 shows the configuration of SRM that consists of three sub-modules: a command interpreter, a speech recognition engine Julius, and a grammar transformer. The … Cited by 7 – Related articles – All 6 versions

A generic framework for target-specific transformation operators in XML transformation languages D Fotsch – Database and Expert Systems Applications, 2007. …, 2007 – ieeexplore.ieee.org … XSLT (the arrows in figure 1). Grammar Transformers The Grammar Transformer produces a rule-based specification in Schematron from the grammar-based XML Schema document. The paradigm shift is necessary because … Cited by 1 – Related articles – All 3 versions

[PDF] Anthropomorphic Agent as an Integrating Platform of Audio-Visual Information [PDF] from nishimotz.com S Sagayama, T Nishimoto – 2003 – hil.nishimotz.com … the model parameters are trained, facial expressions and voice quality can be controlled easily. 2.2.2 Speech recognition module (SRM) SRM consists of three submodules: the command interpreter, the speech recognition engine, and the grammar transformer. … Cited by 3 – Related articles – View as HTML – All 4 versions

Review of the environments symposium K Reed – ACM SIGSOFT Software Engineering Notes, 1987 – dl.acm.org … The result is an extension to Gandalf’s [Stau1986a] structure-oriented environment generator functioning as an AloeGen [Gar11986a] extension which allows a grammar transformer to be generated and then applied to an existing grammar. … Cited by 2 – Related articles

Off-and-on tokens C Clark – ACM SIGPLAN Notices, 2000 – dl.acm.org … don’t. ws-star: // empty I ws ws-star ws-plus: ws I WS ws-plus 3.2 A Subtle Catch The grammar transformer proposed above makes two mistakes. It inserts a ws* between id and the left paren in the first #define alternative. It also … Cited by 1 – Related articles – All 2 versions

System and method for implementation of the YK lossless data compression algorithm using a modular computational architecture S Goel… – US Patent 6,492,917, 2002 – Google Patents Page 1. IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIW US006492917B1 (12) United States Patent ao) Patent No.: us 6,492,917 bi Goel et al. (45) Date of Patent: Dec. 10,2002 (54) SYSTEM AND METHOD FOR IMPLEMENTATION OF THE YK … Cited by 3 – Related articles – All 2 versions

[PDF] Set-Constraint-Based Analysis by Abstract Interpretation [PDF] from snu.ac.kr J Shin – ropas.snu.ac.kr … ROPAS Weekly Show & Tell (2005-01-03) – Set-Constraint-Based Analysis by Abstract Interpretation – p. 21/27 Page 22. Example: Grammar Transformer Grammar transformer Fgr ? Dgr ? Dgr for the example program is Fgr (<T, N, P>) = <T ? {0, a,b,c,cons,nil}, N ? {X }, … Related articles – View as HTML – All 2 versions

[CITATION] Universite de Nice Nice, France O Lecarme – Methods of algorithmic language implementation, 1977 – Springer Related articles

Precedence Grammar and Its Transformation S Wang, L Jin… – Information and Communication …, 2006 – ieeexplore.ieee.org … 3.2 Grammar Transformer Our algorithm is a state-based method, so the thing to be discussed first is what is a state, and then the concept of state transition machine will be introduced. The following are their formal definitions. …

[CITATION] INFORMATION PROCESSING 71-NORTH-HOLLAND PUBLISHING COMPANY (1972) O LECARME… – … of the IFIP congress 71 organized …, 1972 – North-Holland Related articles – All 2 versions

[PDF] Writing and Designing C++ Extensions with Transformers [PDF] from epita.fr V Ordy – 2009 – lrde.epita.fr Page 1. Writing and Designing C++ Extensions with Transformers Vincent Ordy Technical Report no0913, December 2009 revision 2154 The Transformers project aims at providing source to source transformations for C and C++ languages. … Related articles – View as HTML

[PDF] A calculus for modular and extensible language definition in [PDF] from psu.edu R Lämmel… – Citeseer … In the sequel we will suggest AG specification based on • a context-free grammar • transformer declarations describing components (subtypes) of attributions, and • exceptional GSF rules based on levels. By a process of lifting a GSF scheme of a desired type can be derived. … Related articles – View as HTML – All 5 versions

The tree equivalence problem for linear recursion schemes V Sabelfeld – Perspectives of System Informatics, 1996 – Springer … For an address a of a call F(tl,… ,tn) in a scheme we define the grammar transformer ~call(a)~ : s U Vat(A)) –~ s U Vat(A)). … Finally, define ~call(a)~G de_=l Red(G’). Lemma 2. For all addresses a of a scheme, ~call(a)] is a distributive grammar transformer, ie … Related articles – BL Direct – All 3 versions

[PDF] Identification of Patterns through Haskell Programs Analysis [PDF] from eucip.pl J Kollár, S Chodarev, E Pietriková… – fedcsis.eucip.pl … B. Transformation of Haskell 98 Grammar To be able to process the grammar programmatically, it is required to transform HTML form of grammar to more suitable representation. To transform the Haskell grammar to the appropriate form, a grammar transformer was created. … Related articles – View as HTML

[PDF] AT&T Labs, 101 Crawfords Corner Road, Holmdel, NJ 07733, USA yann@ research. att. com [PDF] from psu.edu Y Le Cun, L eon Bottou… – Citeseer … The grammar transformer Tgram selects the paths of the recognition graph that represent valid character sequences for check amounts. … The output of the grammar transformer, called the interpretation graph, contains all the paths in the recognition graph that … Related articles – View as HTML – All 3 versions

[PDF] Forwards and backwards analysis for functional programs [PDF] from psu.edu A Sabelfeld… – Citeseer Page 1. Forwards and backwards analysis for functional programs Andrei Sabelfeld Chalmers University of Technology G oteborg, Sweden andrei@cs.chalmers.se Viktor Sabelfeld Karlsruhe University Karlsruhe, Germany sabelfel@ira.uka.de … Related articles – View as HTML – All 10 versions

Compiler construction for digital computers, David Gries, Wiley, New York, 1971. No. of pages: 493. Price:£ 5.75 KV Hanford – Software: Practice and Experience, 1972 – Wiley Online Library … The statement that there is nothing formal or automatic about the method of recursive descent for parsing would seem to be disproved by the automatic grammar transformer described by Foster (Automatic Syntactic Analysis, Macdonald-Elsevier)-inci- dentally, Foster’s book … Related articles

[PDF] Using hands-on visualizations to teach computer science from beginning courses to advanced courses [PDF] from psu.edu SH Rodger – Second Program Visualization Workshop, 2002 – Citeseer … Page 6. We mention several other tools that can be used for teaching automata theory with hands-on visualization. Pâté [4] is a tool for parsing restricted and unrestricted grammars and a grammar transformer from a context- free grammar to Chomsky Normal Form. … Cited by 11 – Related articles – View as HTML – All 5 versions

Modular programming, J. Maynard, Butterworths, London, 1971. No. of pages: 100. Price:£ 1.50 DW Barron – Software: Practice and Experience, 1972 – Wiley Online Library … The statement that there is nothing formal or automatic about the method of recursive descent for parsing would seem to be disproved by the automatic grammar transformer described by Foster (Automatic Syntactic Analysis, Macdonald-Elsevier)-inci- dentally, Foster’s book … Related articles

[PDF] Eliminating Dead Computations on Recursive Data [PDF] from psu.edu YA Liu – 1997 – Citeseer … The method represents partially dead recursive data using projections based on general regular tree grammars extended with the notion of live and dead. The analysis is de ned as mu- tually recursive grammar transformers that capture exact backward dependencies. … Related articles – View as HTML – All 20 versions

[CITATION] FRANCE TELECOM CNET DTLIMSV R Groz… – … techniques and protocol specification, testing and …, 1997 – CRC Press Related articles

Module for constructing trainable modular network in which each module inputs and outputs data structured as a graph Y Bengio, L Bottou… – US Patent 6,128,606, 2000 – Google Patents Page 1. United States Patent Bengio et al. [19] US006128606A [ii] Patent Number: [45] Date of Patent: 6,128,606 Oct. 3,2000 [54] MODULE FOR CONSTRUCTING TRAINABLE MODULAR NETWORK IN WHICH EACH MODULE … Cited by 17 – Related articles – All 2 versions

Eliminating dead code on recursive data [PDF] from psu.edu Y Liu… – Static Analysis, 1999 – Springer Page 1. Eliminating Dead Code on Recursive Data Yanhong A. Liu* and Scott D. Stoller? Computer Science Department, Indiana University, Bloomington, IN 47405 {liu,stoller}@cs.indiana.edu Abstract. This paper describes … Cited by 17 – Related articles – BL Direct – All 33 versions

Relational constraint: A fast semantic analysis technique [PS] from cornell.edu AB Webber – 1992 – ecommons.cornell.edu … It is an iterative process, and Thinner takes as much time as the user gives it: the more time it has, the more optimizations it may discover. The grammar transformer works with a counterexample: a trace graph that has been shown to include unnecessary computation. … Cited by 2 – Related articles – Library Search – All 5 versions

[CITATION] Athen’s system George ?, PAPAKONSTANTINOU Computer Center Greek Atomic Energy Commission AP Attikis – REVIEW OF EXISTING SYSTEMS, 1986

[PS] Compiler Generation [PS] from back2roots.org J Grosch – 1992 – back2roots.org … lalr directly accepts only grammar rules in plain BNF notation. If the grammar uses EBNF constructs such as |, +, * or [] it has to be converted to plain BNF by the grammar transformer bnf. … In this case the grammar transformer bnf is necessary, again. … Cited by 2 – Related articles – View as HTML – All 11 versions

The Elegant compiler generator system L Augusteijn – Attribute Grammars and their Applications, 1990 – Springer … system is comprised of a scanner generator ScauGen [Aug89c], a parser and attribute evaluator generator Elesant [Aug89b], a domain type generator TypeGen [Aug89d], a back-end generator CodeGen [Aug89a] and of an EBNF to attribute grammar transformer Bar [Mor89]. … Cited by 27 – Related articles – All 4 versions

COPS and COPS 2 J BOROWIEC – Attribute grammars: definitions, systems, and …, 1988 – books.google.com … Page 77. cws 65 CWS2 ”Attribute’ ^ Grammar; Grammar transformer and Parser generator semantic attributes . nd semantic action I compiler generator|^ generation time evaluation time 4. Optimizations None required. 5. Applications Teaching. …

[PDF] SPIRE: A Sequential to Parallel Intermediate Representation Extension [PDF] from ensmp.fr D Khaldi, P Jouvelot, C Ancourt… – 2012 – cri.ensmp.fr … 5.1 SPIRE Core Language Fundamentally, at the syntactic level, SPIRE is a grammar transformer, mapping the definition of a sequential language Stmt to its synchronized version SPIRE(Stmt) defined by: S ? SPIRE(Stmt) ::= nop | I=E | S1;S2 | loop(E,S) | (1) … Cited by 1 – View as HTML

[BOOK] No Stinkin’Grammar JM Nixon – books.google.com Page 1. An Essay on Learning English: Language An Exceptional Ph. D. Joseph M. Nixon, Page 2. No Stinkin’ Grammar Page 3. Page 4. No Stinkin’ Grammar An Essay on Learning English: An Exceptional Language Joseph M. NixoN, ph. D. Page 5. …

Implicit phasing for library dependencies [PDF] from umi.com A Ghuloum – 2009 – gradworks.umi.com Page 1. IMPLICIT PHASING FOR LIBRARY DEPENDENCIES ABDULAZIZ GHULOUM SUBMITTED TO THE FACULTY OF THE UNIVERSITY GRADUATE SCHOOL IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR … Related articles – All 4 versions

[PDF] Using filters for the disambiguation of context-free grammars [PDF] from psu.edu P Klint, E Visser – Proc. ASMICS Workshop on Parsing Theory, 1994 – Citeseer … rules). Generation phase: a grammar transformer and a parser generator. Typical grammar transformations are the elimination of left/ right recursion, and the coding of priority and associativity information in grammar rules. Parser … Cited by 50 – Related articles – View as HTML – All 20 versions

[PDF] From context-free grammars with priorities to character class grammars [PDF] from psu.edu E Visser – Liber Amicorum Paul Klint. CWI, Amsterdam, …, 1997 – Citeseer … 1.3 Grammar Transformation In this paper we introduce a grammar transformation to interpret priorities. The advantage of this method is that it simplies the parser generator by shifting the computation with priority rules from the parser generator to a grammar transformer. … Cited by 2 – Related articles – View as HTML – All 14 versions

Embedded parser generators [PDF] from chalmers.se J Duregård… – Proceedings of the 4th ACM symposium on …, 2011 – dl.acm.org … In this case the type of f indicates that it is a grammar transformer but one could also have functions that do not take an existing grammar as an argument (ie constant grammars) or one that takes some other parameter like a list of operators and constructs grammar from that (ie … Related articles – All 3 versions

Systemic classification and its efficiency [PDF] from upenn.edu C Brew – Computational Linguistics, 1991 – dl.acm.org Page 1. Systemic Classification and its Efficiency Chris Brew” Department of Experimental Psychology and Human Communication Research Centre This paper examines the problem of classifying linguistic objects on the basis … Cited by 24 – Related articles – Library Search – All 22 versions

[DOC] 1. Pengumpulan bahan dan source [DOC] from eepis-its.edu BABIIT PENUNJANG, PDANP BAB III… – student.eepis-its.edu … Namun dalam pembahasan ini akan dikhususkan untuk membahas Modul untuk Pengenalan Wicara atau disebut dengan Speech Recognition Module (SRM), SRM Tediri dari tiga modul, yaitu : Command Interpreter, Speech Recognition Engine, Dan Grammar Transformer. … Related articles – View as HTML – All 3 versions

Marco para la transformación de modelos basado en gramáticas de atributos [PDF] from ucm.es JP Gracia Benítez – 2010 – eprints.ucm.es … In order to achieve this goal, we have developed a framework called Attribute Grammar Transformer – AGT, which includes: a metamodel for representing transformations, a specification language called AGTL (Attribute Grammar Transformer Language), a translator from AGTL … Related articles – All 4 versions

[PDF] Safe Template Processing of XML Documents [PDF] from qucosa.de F Hartmann – 2011 – qucosa.de Page 1. Safe Template Processing of XML Documents Disserta on zur Erlangung des akademischen Grades Doktoringenieur (Dr.-Ing.) vorgelegt an der Technischen Universität Dresden Fakultät Informa k eingereicht von Dipl.-Inform. … Cited by 2 – Related articles – View as HTML