Difference between revisions of "Augmented Syntax Diagram"

From ACL Wiki
Jump to: navigation, search
(External links)
 
(8 intermediate revisions by 5 users not shown)
Line 1: Line 1:
'''Augmented Syntax Diagrams''' (abbreviated ASD) are a cross between [http://en.wikipedia.org/wiki/Augmented_transition_network Augmented Transition Networks] (ATNs) [Woods, 1970; Bates, 1978] and syntax diagrams [Goldberg & Robson, 1983; Jensen & Wirth, 1975].  While ASD grammars are equally as powerful as ATNs, they are conceptually simpler.  They involve fewer primitives, and they permit a grammar to be combined with the lexicon of a language, rather than being represented as a structure separate from the lexicon.  They can represent any context-free grammar, and in addition they can be augmented like ATNs with arbitrary computational tests and actions which are to be performed as utterances are parsed.
+
'''Augmented Syntax Diagrams''' (abbreviated ASD) are a cross between [http://en.wikipedia.org/wiki/Augmented_transition_network Augmented Transition Networks] (ATNs) (Woods, 1970; Bates, 1978) and [http://en.wikipedia.org/wiki/Syntax_diagram Syntax Diagrams] (Goldberg & Robson, 1983; Jensen & Wirth, 1975).  While ASD grammars are equally as powerful as ATNs, they are conceptually simpler.  They involve fewer primitives, and they permit a grammar to be combined with the lexicon of a language, rather than being represented as a structure separate from the lexicon.  They can represent any context-free grammar, and in addition they can be augmented like ATNs with arbitrary computational tests and actions which are to be performed as utterances are parsed.
  
 
The following are the main differences between ASD grammars and ATN grammars:
 
The following are the main differences between ASD grammars and ATN grammars:
Line 18: Line 18:
 
== External links ==
 
== External links ==
 
* [http://www.yorku.ca/jmason/asdindex.htm Augmented Syntax Diagram home page]
 
* [http://www.yorku.ca/jmason/asdindex.htm Augmented Syntax Diagram home page]
 +
* [http://www.asdnetworks.com/ ASD demo site]
  
 
== References ==
 
== References ==
Line 23: Line 24:
 
* Goldberg, A. and Robson, D., Smalltalk-80: The Language and its Implementation, Addison-Wesley, 1983.
 
* Goldberg, A. and Robson, D., Smalltalk-80: The Language and its Implementation, Addison-Wesley, 1983.
 
* Jensen, K. and Wirth, N., Pascal User Manual and Report (2nd Edition), Springer-Verlag, 1975.
 
* Jensen, K. and Wirth, N., Pascal User Manual and Report (2nd Edition), Springer-Verlag, 1975.
 +
* Wikipedia, Syntax Diagram, http://en.wikipedia.org/wiki/Syntax_diagram .
 
* Woods, W.A., Transition network grammars for natural language analysis, Communications of the ACM 13:10 (Oct. 1970), pp. 591-606.
 
* Woods, W.A., Transition network grammars for natural language analysis, Communications of the ACM 13:10 (Oct. 1970), pp. 591-606.
 
  
 
[[Category:Parsing]]
 
[[Category:Parsing]]

Latest revision as of 12:37, 5 December 2012

Augmented Syntax Diagrams (abbreviated ASD) are a cross between Augmented Transition Networks (ATNs) (Woods, 1970; Bates, 1978) and Syntax Diagrams (Goldberg & Robson, 1983; Jensen & Wirth, 1975). While ASD grammars are equally as powerful as ATNs, they are conceptually simpler. They involve fewer primitives, and they permit a grammar to be combined with the lexicon of a language, rather than being represented as a structure separate from the lexicon. They can represent any context-free grammar, and in addition they can be augmented like ATNs with arbitrary computational tests and actions which are to be performed as utterances are parsed.

The following are the main differences between ASD grammars and ATN grammars:

  • ASD networks have node labels but no edge labels. In contrast, ATN networks require both node (state) labels and edge (arc) labels. The node labels of an ASD grammar correspond to the edge labels of an ATN.
  • ASD networks are designed for bottom-up parsing; ATN networks are more suitable for top-down parsing.
  • ASD networks have null or dummy nodes as the counterpart to JUMP arcs in ATN grammars. Both match empty strings in the utterance being parsed.
  • ASD networks require only three kinds of node labels: (1) terminal vocabulary elements, (2) non-terminal vocabulary elements which represent phrase types, and (3) a special symbol, $$, to represent dummy nodes. Instance numbers in node labels distinguish between different nodes that are labeled with the same vocabulary element. In contrast, ATN networks require five kinds of arc labels: (1) PUSH arcs, (2) CAT arcs, (3) WORD arcs, (4) JUMP arcs, and (5) POP arcs, in addition to node labels.
  • ASD networks can be represented in non-graphical form by a single lexicon containing both terminal and non-terminal vocabulary elements. In contrast, ATN networks require a representation for the grammar that is separate from the lexicon.

See also

External links

References

  • Bates, M., The theory and practice of augmented transition network grammars. In Natural Language Communication with Computers, L. Bolc, Ed., Springer-Verlag, 1978, pp. 191-259.
  • Goldberg, A. and Robson, D., Smalltalk-80: The Language and its Implementation, Addison-Wesley, 1983.
  • Jensen, K. and Wirth, N., Pascal User Manual and Report (2nd Edition), Springer-Verlag, 1975.
  • Wikipedia, Syntax Diagram, http://en.wikipedia.org/wiki/Syntax_diagram .
  • Woods, W.A., Transition network grammars for natural language analysis, Communications of the ACM 13:10 (Oct. 1970), pp. 591-606.