Published in: J.G. Chen, ed. Expert Systems Applications and Artificial Intelligence. Technology Transfer Series. IITT International, Gournay-Sur-Marne, France, 1995, p.53-58.

ON GRAPH REPRESENTATION OF SYNTAX DEFINITIONS

Vladimir V. Prokhorov

Head of Laboratory, Institute of Math and Mechanics, Russian Academy of Sciences/Ural Branch

GSP-384, Ekaterinburg, 620219 Russia

E-mail: vpro@convex.ru

Abstract

The approach to visual syntax definitions is proposed. This one realizes the idea of syntax specification (a description of a set of admissible objects) as a construction of the Set theory operations of atomic objects-sets. This approach gives birth to visual representation of syntax in the tree-like graphs form. The language may be used in human-computer interaction to describe knowledge about objects’ classes in:

and in other problems of AI. The computer software complex using the language is discussed.

Keywords: Syntax definition, knowledge representation, AI languages, HCI technology.

Contents:

Introduction

1. Description of the language

2. Examples

3. On Completeness of the Language

4. Ways of Improvement for the Language

5. The Language in Computer Software System

6. Conclusion

7. Acknowledgements

References

Introduction

The problems of knowledge about objects’ syntax representation have significance in many applications of AI. Widespread languages of syntactic definitions are oriented to the generative grammar metaphor, to describing of the algorithm of syntax-admissible object’s construction. The syntax language of Backus-Naur formulas [1] and its versions [2] are most common among text languages. Text representation is not much convenient in many applications. The “syntactic charts” [3] is widespread among graph languages. This visual language is not oriented to structural representations of descriptions. Above-mentioned languages admit defining only context-free languages; but, for example, almost every programming language is context-sensitive.

Considered approach for syntax definition is based on the metaphor of syntax description for the set of syntax-admissible objects as hierarchy of the Set theory operations (but not on metaphor of generative algorithm). This language is exclusively structural. The language admits defining context-sensitive syntax. The language’s idea confirms to the one of the language of “algorithmic p-charts” [5] and to the concept of the p-technology [6]. Primary the foundations of the language were reported in [4].

We turn our attention on special version of the language. This one is oriented to description of objects presented by finite linear sequences of symbols and for context-free grammar. (It is possible make an expansion for more general cases.) We postulate that created syntax description determines some set certainly (thus, we have not problems with recursive definitions of sets).

1. Description of the p-Language

    We give brief illustration to description of the main terms of the syntax language.

1. The Main Elements of the Language

We consider any syntax description as a set of syntax descriptions of some objects-sets (that is, non-terminal symbols for object language).

     <Object’s definition>::=

    This construction assigns a set of syntax-permissible essence given by <Describer> with the text name or pictogram.

    <Describer>::= <Terminal> <Construction>

    <Terminal>::= <Atom> <Reference> <Empty> <Terminal function>

    The term <Atom> corresponds to terminal symbol of the object language.

    <Reference> is a reference on syntactic description of another object or recursive reference on described object itself (that is, it is a reference on non-terminal symbols of object language). We postulate of correctness of given recursive definitions.

    <Construction>::= <General function> <Special Set-theory operation> <Case> <Special element wise operation>

<General function>::=

All kinds of <Construction> are some forms of <General function> with special <Pictographic representation of function>.

2. Set-Theory Operations

<Special Set-theory operation>::= <Alternative> <Interception> <Exception> <Forming-union> <Forming-interception>

3. Conditional Alternative

<Case>::=

Here <Condition> is some logic-valued expression depending on meta-variables (from headers of forming constructions). A value of the first type of <Case> construction is that argument <Describer> that corresponds to true <Condition>. A value of the second type of <Case> construction is that argument <Describer> which corresponds to true ‘<Value> <Set>‘ condition.

4. Element Wise Operations

<Special element wise operations>::= <Placing> <Forming-placing> <Element wise sum>

Above-mentioned constructions are examples of element wise operations. For problems of image descriptions, we can devise designation for picture’s distortions (geometrical transformations and the like).

5. Substitution, Synonymy and Gluing

The <Substitution> gives us semantic equivalence of the “substitution field” (it is a circle of the construction designation) to its <Describer>. The <Substitution> element may be used for assignment of sets in headers of forming, <Condition> elements, and so on.

The term <Gluing> means substitution of sets <Describer>, into branches of the same construction <Object description>, and simultaneously the same element of the set <Describer> is used in all constructions of description. For example,

define a plate with four identical bolts, and pairs of arbitrary bolts respectively.

6. Definition of functions

    Definitions of functions may be given both by traditional means of the Set theory (including logic quantifiers using) and special extension of the language.

    <Definition of function>::=

    The <Iconic representation of function> contains the <List of parameters> or pictographic representation of parameters in its field.

    Elements <Type of parameter> denote sets of possible parameters of the function ("empty"; is in use when area of a definition of function seems is clear by appearance of the <Describer>).

2. Examples

    Let us consider the example of syntax definition of some package for communication (see Figure 1). We use here the constructions "Element wise sum", "General function", "Placing" (in "Concatenation" form), "Forming-concatenation", "Exception", "Gluing", "Synonymy", "Reference".

    Descriptions of classes for the image recognition problems may be similar.

    Figure 1

    Let us consider examples of simplest definition of <Identifier> notion in different syntax languages. We suppose <Letters> and <Digits> have been defined as sets of symbols (letters and digits).

    A description in recursive Backus-Naur Formulas syntax language:

    <Identifier>::= <Letter> <Identifier><Letter> <Identifier><Digit>

    A description in non-recursive (“iterative”) Backus-Naur Formula:

    <Identifier>::= <Letter>[{`Letter> <Digit>}]

    Figure 2

    Figure 3

    Descriptions in our syntax language are shown below (see Figure 2, Figure 3).

3. On Completeness of the Language

    The language under consideration is complete regarding context-free grammar, it permits to describe any context-free language. Some expansion of the language allows us also to reach completeness for context-sensitive grammar.

4. Ways of Improvement for the Language

    The language may be supplemented by additional means for graphical representation of constructions that are represented in text form in described version (such as <Condition> in the <Case> construction). Occasionally it may be introduced graphic sub languages for description of logic formulas, constructions with logical quantifiers, string functions and so on.

    On the other hand it is possible to generalize ideas <Placing>, <Function>, etc. for objects, differing of symbol strings (for example, for visual images, assembled units in mechanical engineering). Sense of these ideas in generalizations may be concerned with showing of spatial placing and geometrical transformations. We wish to note that such language turns out to be near to canons of machine-building drawing and electronic circuits.

5. The Language In Computer Software System

    We have realization of a version of the syntax p-language in computer software system ((see Figure 4). This one is a component of PYTHAGORAS visual programming complex (the complex is based on graph approach and multilanguage hierarchical p -technology). The component uses p -language for syntax description of any text language. For example, user may define syntax terms of a programming language (including context-sensitive, say, Pascal), and check of syntax validity of any text as defined language's object. The complex allows assign pictograms for defined objects, functions, and variables. Graph representation of definitions allows use software by non-programmers and in education with high effectiveness.

    Figure 4

6. Conclusion

    It turns to be productive to use the Set theory approach for syntax definitions where syntax description is an expression (in the Set theory terms) of a set of all syntax-permissible objects through atomic objects-sets. Incidentally, syntax definitions have the form of functional ones. Graph language on the approach basis (it is a language of structural functional diagrams) is visual, clear sensitive and gives rich possibilities for syntax description. The language may be used for defining of syntax of programming languages in publications, in education, etc. Use of the language for human-computer interface purposes is productive too. Development of the language with widening of <Placing>, <Function> notion allows to use it for description a priori knowledge of complex objects in systems of pattern recognition, linguistic processors and other systems of AI.

7. Acknowledgements

The research is funded by the Russian Fund for Fundamental Investigations (code 93-012-989).

Author would like to thank programmers of the software Roman Pekhov and Pavel Mamin. Author would like to thank Regina Spencer Sipple for her assistance in editing of the manuscript.

References

[1] P. Naur (Ed.), Report on the algorithmic language ALGOL 60. Communications of the ACM 3 (1960), p.299-342.

[2] K.I. Iverson, A method of syntax specification. Communications of the ACM 7 (1964), p.588-560.

[3] W. Tailor, L. Turner, and R.A. Waychoff, A syntactical chart of ALGOL 60. Communications of the ACM 4 (1961), p.393-400.

[4] V.V. Prokhorov, On the project of standards for structured-procedural charts of algorithms and syntax diagrams. Proceedings of the IV All-Union Workshop on Development and Application of computer Software for Education, Moscow: 1988, p.23-27.

[5] V.V. Prokhorov, pi-charts — the language of graph representation of algorithms and syntax definitions. The Cybernetics and System Analysis, N2, 1992, p.98-107.

[6] V.V. Prokhorov, On contradictions between wealth and compactness of Languages. Proceedings of “Software Engineering Conference (SRIG-ET’94)”, Los Alamitos CA: IEEE Computer Society Press, p.289-296.