Cited By
View all- Castaño J(2003)LR parsing for global index languages (GILs)Proceedings of the 8th international conference on Implementation and application of automata10.5555/1760230.1760257(269-281)Online publication date: 16-Jul-2003
On the applicability of Global Index Grammars
Pages 15 - 22
Abstract
We investigate Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We discuss some of the structural descriptions that GIGs can generate compared with those generated by LIGs. We show also how GIGs can represent structural descriptions corresponding to HPSGs (Pollard and Sag, 1994) schemas.
References
[1]
A. V. Aho. 1968. Indexed grammars - an extension of context-free grammars. Journal of the Association for Computing Machinery, 15(4):647--671.
[2]
T. Becker and P. Lopez. 2000. Adapting hpsg-to-tag compilation to wide-coverage grammars.
[3]
J. Castaño. 2003. GIGs: Restricted context-sensitive descriptive power in bounded polynomial-time. In Proc. of Cicling 2003, Mexico City, February 16-22.
[4]
J. Castaño. 2003b. Global index grammars and descriptive power. In R. Oehrle and J. Rogers, editors, Proc. of Mathematics of Language, MOL 8. Bloomington, Indiana, June.
[5]
J. Castaño. 2003c. LR Parsing for Global Index Languages (GILs). In In Proceeding of CIAA 2003, Santa Barbara, CA.
[6]
J. Dassow and G. Pǎun. 1989. Regulated Rewriting in Formal Language Theory. Springer, Berlin, Heidelberg, New York.
[7]
J. Earley. 1970. An Efficient Context-free Parsing Algorithm. Communications of the ACM, 13:94--102.
[8]
G. Gazdar. 1988. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69--94. D. Reidel, Dordrecht.
[9]
M. H. Harrison. 1978. Introduction to Formal Language Theory. Addison-Wesley Publishing Company, Inc., Reading, MA.
[10]
A. Joshi, K. Vijay-Shanker, and D. Weir. 1991. The convergence of mildly context-sensitive grammatical formalisms. In Peter Sells, Stuart Shieber, and Thomas Wasow, editors, Foundational issues in natural language processing, pages 31--81. MIT Press, Cambridge, MA.
[11]
A. Joshi. 1985. Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural description? In D. Dowty, L. Karttunen, and A. Zwicky, editors, Natural language processing: psycholinguistic, computational and theoretical perspectives, pages 206--250. Chicago University Press, New York.
[12]
A. Joshi. 2000. Relationship between strong and weak generative power of formal systems. In Proceedings of the Fifth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+5), pages 107--114, Paris, France.
[13]
R. Kasper, B. Kiefer, K. Netter, and K. Vijay-Shanker. 1995. Compilation of HPSG into TAG. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, pages 92--99. Cambridge, Mass.
[14]
P. Miller. 1999. Strong Generative Capacity. CSLI Publications, Stanford University, Stanford CA, USA.
[15]
C. Pollard and I. A. Sag. 1994. Head-driven Phrase Structure Grammar. University of Chicago Press, Chicago, IL.
[16]
G. Satta. 1994. Tree-adjoining grammar parsing and boolean matrix multiplication. Computational linguistics, 20, No. 2.
[17]
M. Tomita. 1987. An efficiente augmented-context-free parsing algorithm. Computational linguistics, 13:31--46.
[18]
K. Vijay-Shanker, D. J. Weir, and A. K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proc. of the 25th ACL, pages 104--111, Stanford, CA.
[19]
D. Weir. 1988. Characterizing mildly context-sensitive grammar formalisms. Ph.D. thesis, University of Pennsylvania.
- On the applicability of Global Index Grammars
Recommendations
Global Index Grammars and Descriptive Power
We review the properties of Global Index Grammars (GIGs), a grammar formalism that uses a stack of indices associated with productions and has restricted context-sensitive power. We show how the control of the derivation is performed and how this ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languagesFor decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Association for Computational Linguistics
United States
Publication History
Published: 07 July 2003
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 85 of 443 submissions, 19%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 217Total Downloads
- Downloads (Last 12 months)59
- Downloads (Last 6 weeks)11
Reflects downloads up to 29 Jan 2025
Other Metrics
Citations
Cited By
View all- Castaño J(2003)LR parsing for global index languages (GILs)Proceedings of the 8th international conference on Implementation and application of automata10.5555/1760230.1760257(269-281)Online publication date: 16-Jul-2003
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in