IEICE TRANSACTIONS on Information
OAG*: Improved Ordered Attribute Grammars for Less Type 3 Circularities
Summary :
Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.4 pp.673-685
- Publication Date
- 2003/04/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Theory of Automata, Formal Language Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shin NATORI, Katsuhiko GONDOW, Takashi IMAIZUMI, Takeshi HAGIWARA, Takuya KATAYAMA, "OAG*: Improved Ordered Attribute Grammars for Less Type 3 Circularities" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 4, pp. 673-685, April 2003, doi: .
Abstract: Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_4_673/_p
Copy
@ARTICLE{e86-d_4_673,
author={Shin NATORI, Katsuhiko GONDOW, Takashi IMAIZUMI, Takeshi HAGIWARA, Takuya KATAYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={OAG*: Improved Ordered Attribute Grammars for Less Type 3 Circularities},
year={2003},
volume={E86-D},
number={4},
pages={673-685},
abstract={Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - OAG*: Improved Ordered Attribute Grammars for Less Type 3 Circularities
T2 - IEICE TRANSACTIONS on Information
SP - 673
EP - 685
AU - Shin NATORI
AU - Katsuhiko GONDOW
AU - Takashi IMAIZUMI
AU - Takeshi HAGIWARA
AU - Takuya KATAYAMA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2003
AB - Ordered attribute grammars (OAGs for short) are a useful class of attribute grammars (AGs). For some attribute grammars, even though they are not circular, OAG circularity test reports that they are not ordered and fails to generate attribute evaluators because some approximation introduces circularities (called type 3 circularities in this paper). First we discuss that it is sometimes difficult for programmers to eliminate type 3 circularities by hand. Second, to reduce this difficulty, we propose a new AG class called OAG* that produces less type 3 circularities than OAG while preserving the positive characteristic of OAG. OAG* uses a global dependency graph GDS that provides a new approximation algorithm. We obtained good results with our experimental implementation of OAG*. It is shown that OAG* is different from the existing GAG and Eli/Liga systems. Finally, two combinations of Eli/Liga and OAG* are provided.
ER -
English
