Every programming language has its own syntax rules. Such rules can be represented with either the Backus-Naur form (BNF) notation or with a Syntax diagram (also called a Railroad diagram). BNF uses text-based mathematical notations for defining those rules, while a Syntax diagram employs a graphical approach. Converting any of the two techniques to an algorithm or computer program is somewhat difficult for students due to the recursive expressions used by each of the techniques in defining the syntactic rules of a grammar. The aim of this work is therefore to showcase how an algorithm for one of such techniques (namely, a syntax diagram) can be written for easy understanding and implementation with a computer. A Finite State automata (FSA) approach was adopted by the researcher for modelling any given grammatical rule of a programming language for easy implementation with a computer. The grammatical rules for generating an integer number was arbitrarily selected by the researcher, amongst other rules, for formulating the required algorithm. The algorithm (which is a pseudocode) was written to be in tandem with the FSA model for easier understanding and programming. Results showed that when the pseudocode is implemented with a computer with some trial data, every data that conformed with the grammatical rules for generating integer numbers was accepted as ”valid integer”, while other incoherent ones were declared “invalid integer”. This helps in smoothening the understanding of students of any rigorous or recursive problem for easy implementation with a computer.
A Backus-Naur form is a notation used in the field of Computer Science to express the syntax of a programming language [1]. The expression contains a list of all the rules that defines a particular grammar of a programming language. The three basic symbols used by the BNF are: ::= (which means, “is defined as”) | (which means, “Or”) < > (angular brackets that contain a category name) For instance, to use the BNF to define the grammatical rules for generating an unsigned integer number, we have the following structure: <pinteger> ::= <no> <no> ::= <digit><no> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 In plain English, the first line of figure 1 states that an unsigned integer, <pinteger>, is defined as a number, <no>. The second line contains two rules which state that: (i) <no> is defined as <digit> followed by <no> , or (ii) <no> is defined as <digit>. The third line contains 10 rules which state that <digit> is defined as ‘0’ or ‘1’ or ‘2’ or ‘3’ or ‘4’ or ‘5’ or ‘6’ or ‘7’ or ‘8’ ‘9’. The above grammar contains a total of 13 rules. Each rule has a left part and a right part. The ‘left part’ defines the ‘right part’. Any symbol appearing on the left part (or both parts) of a rule is called a non-terminal symbol, while any symbol that appears only on the right part (but not on both parts) of a rule is called a terminal symbol. In other words, the terminal symbols are the sentences (or string) that can be derived from a grammar. The first non-terminal symbol is called the start symbol. All generation of sentences of a grammar commences from the start symbol. In figure1, the start symbol is <pinteger>. According to [2],
The Backus-Naur Form is a way of defining syntax. It consists of • a set of terminal symbols • a set of non-terminal symbols • a set of production rules of the form, Left-Hand-Side ::= Right-Hand-Side where the LHS is a non-terminal symbol and the RHS is a sequence of symbols (terminals or non-terminals).
In figure1, the set of non-terminal symbols are, {<pinteger>, <no>, <digit>}, while the set of terminal symbols are, {0,1,2,3,4,5,6,7,8,9}. The grammar contains a recursive definition of how to generate an unsigned integer number, as shown in the second line of the grammar. Such recursive expression appears somewhat difficult for an ordinary person to easily understand, not to talk of converting it to an algorithm or computer program. According to William [3], recursion is often regarded as a deep mystery by novices in mathematics or computing, and so aught to be reserved for more advanced courses. The same recursive scenario occurs when the grammar of figure 1 is represented with a syntax diagram, as shown in figure 2.
<pinteger> <no> <digit> <no> <no> A ‘parse tree’ shows how valid (or invalid) sentences can be derived (or non derivable) from a grammar, as shown in figure 3 and figure 4, respectively for the derivation of the string, 614 and 2T from the grammar defined in figure 1 (using BNF) or figure 2 (using syntax <digit>
<no> In Computer Science, recursion is typically used for solving problems that involve recursive relations (such as the generation of integer numbers shown in figure 1 and figure 2 of section1). According to [3], “The concept of recursion comes from mathematics where we often encounter recursive relations”. For example, consider the problem of raising a real number, X, to an integer power, N. The problem can be solved recursively by stepwise refinement (i.e. breaking a problem down into simpler computational parts), as shown in table 1.
Thus, each recursive step is a simpler version of the initial problem. The process continues until a termination point is reached (i.e. X0 = 1 in the above example) where no further recursive process occurs, and the final result then determined by backward substitution. The above problem can be solved programmatically using a Java function as follows: public static double power(double X, int N) { if(N = = 0) { return 1.0; return X * power(X, N-1); } } else { } Thus, we can see that, recursion is a process of breaking a computation down in such a way that a simpler computation of the same kind with the previous problem is derived, and the decomposition process continues until a trivial stage is reached. Simply put, [4] explains that, “Recursion is a process whereby a function calls itself inside its body for the execution of a task until a base case is reached”. The beauty of recursion is that it presents a clearer, intuitive, and simpler solution to a problem which would have been very difficult or too clumsy to solve through other means [5]. For instance, a popular mathematical puzzle called ‘The towers of Hanoi’ can be easily solved with recursion, as elegantly illustrated by [5], [3], and [6], to mention a few. The puzzle would have been too clumsy or nasty to solve through other means such as Iteration.
The BNF notation, according to [7], was named after the two inventors: John Backus of the United States of America, and Peter Naur of Denmark. The notation makes extensive use of recursion in defining the syntax of a programming language very succinctly. The mystery behind recursion can be demystified by understanding it as a stepwise refinement of the initial problem (by divide-and-conquer technique) until a trivial case (or terminal point) is reached that requires no further simplification. There are [now] many variants and extensions of BNF, generally either for the sake of simplicity and succinctness, or to adapt it to a specific application, [8]. Typical examples of these variants are given by [9] as, “Extended BNF (EBNF) notation”, “Augmented BNF (ABNF) notation”, and “Regular extensions to BNF notation”. The EBNF notation is almost a superset of BNF, and is now the most commonly used structure for describing the grammar of a language. On the other hand, the ABNF notation is commonly used for describing the Internet Engineering Task Force (IETF) protocols; while the Regular extensions to BNF notation are popularly used by the Python programming language for its lexical specifications. Table 2 shows some of the basic differences amongst these notations. , The syntax diagram is used to represent the BNF notation pictorially for easier understanding, whereby each of the non-terminal symbols in a grammar is represented as a block or module that performs a given task, as earlier illustrated in figure 2. By the words of [10], “A syntax diagram is a pictorial method of representing the format of components in a programming language, and the direction of the arrowed lines indicates the order in which the diagram is to be read or followed”. This is where the use of Finite State Automata (FSA) becomes very necessary in showing pictorially, as well as in a more compact form, how the sentences (or terminal symbols) of a grammar can be generated for easy implementation with a computer. The use of FSA defines the syntax of a grammar as well as its recursive processes very clearly so that valid or invalid sentences can easily be identified. According to [11],
A finite state automata (FSA) is a simple idealized machine that recognizes patterns from the input [which consists of finite string of symbols] taken from some character set (or alphabet). The job of an FSA is to accept or reject an input depending on whether the pattern defined by the FSA occurs in the input According to [12], an FSA (simply denoted as, M) consists of 5 components: M = (Q, ∑, q0, δ, F), where, ▪ ▪ ▪ ▪
Q is a finite set of states ∑ is the input alphabet q0 ϵ Q is the start state F ϵ Q is the set of final or accepting states whitespa ce same as BNF result= score result ::=
score CGPA = digit CGPA:: = “.” digit digit “.”
digit name =[title] next name::=[ti tle] next title = *(“mr”/ “mrs”/ others} age =1*digit; age = 1*3digit; title :: = (“mr” | “mrs” | others)? age::= digit+ age :: = digit1*3 δ is a transition function that takes up a pair of state and input symbol (say, <q,a>) in order to determine the next state (say q՛) for the machine; i.e., δ(q,a) = q՛ The above representation conforms perfectly with the generation of sentences using the syntax diagram or BNF notation, as shown in table 3. This work therefore showcases how the FSA can be used to model a syntax diagram/BNF notation for easy conversion to a computer program. 3.
The syntax for generating signed or unsigned integer numbers using the syntax diagram or the BNF notation was used by the researcher to illustrate how such rules can be implemented programmatically. Figure 6 shows the syntax for generating signed or unsigned integer numbers using the BNF notation. <int> ::= + <no> | – <no> | <no> <no> ::= <digit><no> | <digit> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 The syntax diagram representation of figure 6 is shown in the following figure 7. We can use a finite state automata to model any of the two techniques, as shown in figure 8.
Variable description
P = plus (+) sign P՛ = not a plus sign
m = minus (-) sign m՛ = not a minus sign
d = digit (
belongs to state(3); the FSA therefore moves from state(0) to state(3). the 2nd character of the string is digit(2) which also belongs to state(3); the FSA therefore moves from state(3) to state(3) – a recursive movement or transition. The 3rd character of the string is digit(5) which again belongs to state(3); the FSA therefore makes another recursive transition from state(3) to state(3). The last character of the string is the <enter key> which belongs to state(4); the FSA therefore moves from state(3) to state(4) – the ‘Accept state’. The string, 725, is subsequently accepted as VALID integer.
Similarly, the second input string, – 6A31<enter key>, is parsed as follows: at state(0), the finite state automata (FSA) receives the input string supplied by the user; the 1st character of the string is a minus(–) sign which belongs to state(2); the FSA therefore moves from state(0) to state(2). the 2nd character of the string is digit(6) which belongs to state(3); the FSA therefore moves from state(2) to state(3). The 3rd character of the string is letter(A) which belongs to state(5) – ‘Error or Reject state’ because the received character is d՛ (i.e. not a digit); the FSA therefore moves from state(3) to state(5). Subsequently, the string, –6A31, is rejected as INVALID integer (without parsing the remaining characters, ‘31’, in the string).
Lastly, the input string, +9<enter key>,
is parsed as follows: at state(0), the
finite state automata (FSA) receives the
input string supplied by the user; the 1st
character of the string is a plus(+) sign
which belongs to state(
The pseudocode for implementing the finite state automata of figure 8 is shown in figure 9 that follows. Valid integer Error (invalid integer).
The symbol, ‘A’ is illegal Valid integer The input string, 725<enter key>, is parsed as follows: at state(0), the finite state automata (FSA) receives the input string supplied by the user; the 1st character of the string is digit(7) which
-946890 +73.6 +152 -600 496+ 8112 16 – 4 1,500 The use of automata machine to model the generation of integer numbers (which are defined recursively by a syntax diagram or BNF notation) makes the programming aspect of its implementation very easy to write and understand. The 6 states in the machine were well represented in the program (as functions that perform specific tasks) so that any character that goes contrary to the rules of the grammar is reported by state(5) as an error, and the parsing process is terminated immediately without processing the remaining part of the input string (if any). For instance, the input string, ‘+73.6’ in the sample output of table 4 is ‘WRONG integer’ because the decimal point(.) is not defined in the grammar being represented by the automata machine. Again, the input string, ‘496+’ is ‘WRONG integer’ because the order of arrangement of the characters does not agree with the syntax of the grammar. On the other hand, any input string that transits successfully from state(0) to state (4) is accepted as VALID integer because it agrees with the syntax of the grammar in (i) order of arrangement, and (ii) in symbols.
Recursion is a powerful mathematical technique used ubiquitously in Computer science. The BNF notation or syntax diagram employs it extensively in defining the grammatical rules of a programming language. The use of Finite State Automata (FSA) in transforming the ‘terminals’ and ‘production rules’ of a grammar into a directed graph helps immensely in modelling the grammar into a very compact form for easier understanding and programming. “Grammar_The language of languages(BNF, EBNF, ABNF, and more)”, 2020. URL: http://matt.might.net/articles/gramma rs-bnf-ebnf/