Structural Analysis of Mathematical Formulae with Verification Based on Formula Description Grammar
16
Citation
11
Reference
10
Related Paper
Citation Trend
Keywords:
Representation
Parse tree
Tree (set theory)
Hierarchical A* (HA*) uses of a hierarchy of coarse grammars to speed up parsing without sacrificing optimality. HA* prioritizes search in refined grammars using Viterbi outside costs computed in coarser grammars. We present Bridge Hierarchical A* (BHA*), a modified Hierarchial A* algorithm which computes a novel outside cost called a bridge outside cost. These bridge costs mix finer outside scores with coarser inside scores, and thus constitute tighter heuristics than entirely coarse scores. We show that BHA* substantially outperforms HA* when the hierarchy contains only very coarse grammars, while achieving comparable performance on more refined hierarchies.
Heuristics
Bridge (graph theory)
Cite
Citations (6)
Parse trees are an essential internal construct of the q language. They are a nested list – or collection – of functions and their arguments, which can be executed when desired and are expressed in the form of (func;arg1;arg2;.). Understanding parse trees is useful in becoming fluent with such expressions. Knowledge of parse trees is useful in appreciating the full elasticity of q and giving us access to its full repertoire. This chapter introduces parse trees and then focuses on the functional evaluation of q-SQL queries. There are two critical native operators which the authors need to know to be able to work with parse trees: eval and parse. Read-only evaluation is performed with the function reval which has the same signature as eval. The verb reval simulates the effect of launching q with option -b, when accessing the instance remotely and running eval.
Parse tree
Cite
Citations (0)
Abstract syntax trees were devised as a compact alternative to parse trees, because parse trees are known to require excessive amounts of storage to represent parsed programs. However, the savings that abstract syntax trees actually achieve have never been precisely described because the necessary analysis has been missing. Without it, one can only measure particular cases that may not adequately represent all the possible behaviors. We introduce a data structure, production trees, that are more compact than either abstract syntax trees or parse trees. Further, we develop the necessary analysis to characterize the storage requirements of parse trees, abstract syntax trees, and production trees and relate the size of all three to the size of the program's text. The analysis yields the parameters needed to characterize these storage behaviors over their entire range. We flesh out the analysis by measuring these parameters for a sample of “C” programs. For these programs, production trees were from 1/15 to 1/23 the size of the corresponding parse tree, l/2.7 the size of a (minimal) abstract syntax tree, and averaged only 2.83 times the size of the program text.
Parse tree
Tree (set theory)
Syntax error
Representation
Cite
Citations (5)
Parse tree
Cite
Citations (10)
Parse tree
Formalism (music)
Tree (set theory)
Cite
Citations (0)
The present paper describes an alternative algorithm for the removal of erasing rules from E0S grammars. As opposed to the standard way of eliminating erasing rules in most E0S-like grammars, such as context-free grammars, this method requires no predetermination of symbols that derive the empty string. The proposed algorithm is formally verified. In the conclusion of the paper, the applicability of the algorithm to E0S grammars that work in a semi-parallel way is demonstrated. Furthermore, two open problems are formulated.
Indexed grammar
Definite clause grammar
Embedded pushdown automaton
Cite
Citations (0)
Stochastic context-free grammar
Embedded pushdown automaton
Indexed grammar
Cite
Citations (4)
Indexed grammar
Embedded pushdown automaton
Definite clause grammar
Stochastic context-free grammar
Similarity (geometry)
Cite
Citations (3)
This paper discusses path controlled grammars—context-free gram- mars with a root-to-leaf path in their derivation trees restricted by a control language. First, it investigates the impact of erasing rules on the generative power of path controlled grammars. Then, it establishes two Chomsky-like normal forms for path controlled grammars—the first allows unit rules, the second allows just one erasing rule.
Indexed grammar
Cite
Citations (0)