<p>I agree with @Buffy's comment. If your goal is to teach the concepts of lexical rules and context-free grammar, I would focus on that rather than on using tools to build parsers from those grammar rules.</p>

<p>I've found that if you have first taught regular expressions and finite automata, that you can teach these concepts quite nicely within that scope using toy languages that you invent and derive in class.</p>

<p>For example, you could create a language defined as:</p>

<pre><code>L = {w | w is a pair of positive integers which are added or subtracted}
</code></pre>

<p>For example, these would all be valid strings in such a language: { "3 + 2", "5 - 1", "0 + 2", ... }</p>

<p>Then you could define your grammar by deciding what set of variables (V), set of terminals (Σ), set of substitution rules (R), and start variable (s) you need to describe that language. </p>

<pre><code>G = (V, Σ, R, s)
</code></pre>

<p>This can all be done in a class or group discussion on paper (or whiteboard) without any tools. I find it easiest for students to come up with Σ first, then use that to deduce the members of <em>V</em>, then <em>R</em>, then s.</p>

<p>A guided discussion could go something like:</p>

<h1><em>Σ</em></h1>

<p>"Let's decide what kinds of things we could see in our set of terminals, what symbols (some people refer to these as tokens, though parsers think of these differently) would we see in this language?"</p>

<p>...</p>

<p>"According to our definition of L, this could be any positive integer, a plus, or a minus. So the set <em>Σ</em> could be defined as:"</p>

<pre><code>{ℤ+, +, -}
</code></pre>

<h1><em>V</em></h1>

<p>"Now, how could we group these things together?"</p>

<p>...</p>

<p>"The things we're seeing are either <em>positive-integer</em> things, or <em>Operator</em> things, a valid <em>Expression</em> in our language always appears in this form:</p>

<pre><code>Expression -&gt; positive-integer Operator positive-integer
</code></pre>

<p>Since the set of things that can be a positive-integer is already represented by ℤ+ in our set of terminals (<em>Σ</em>), that leaves only two types of things in our set of variables:</p>

<pre><code>{ Expression, Operator }
</code></pre>

<h1><em>R</em></h1>

<p>"Now, let's come up with the substation rules for this language. We already said that:</p>

<pre><code>Expression -&gt; positive-integer Operator positive-integer
</code></pre>

<p>"Since <em>positive-integer</em> is a terminal, we just need a set of rules for <em>Operator</em>. What kinds of things can an Operator be?"</p>

<p>...</p>

<pre><code>Operator -&gt; +
Operator -&gt; -
</code></pre>

<p>"So that means the complete set of rules is:"</p>

<pre><code>Expression -&gt; positive-integer Operator positive-integer
Operator -&gt; +
Operator -&gt; -
</code></pre>

<h1>s</h1>

<p>"Now, we just need to decide what the starting variable should be. Which element of <em>V</em> should be our top-level item?"
...
"Expression"</p>

<h1>Next Steps</h1>

<p>From this point, you can then walk through derivations for the grammar. Depending on where you want to go next, you could then illustrate the grammar as a finite automata or as a parse tree, or express it in Backus-Naur form.</p>

<p>If you still want to discuss parsers, I've also given students assignments where I provide them with a simple grammar definition like the above, and ask them to implement a DFA that can determine if a provided string is a valid expression in the language. This is a lot easier if you've already discussed regular expressions.</p>

CC BY-SA 4.0
2020-06-08T21:53:35.933Z
Answers like this are why I love this community. You clearly have experience teaching the subject.  Very useful!
Ben I.
CC BY-SA 4.0
2020-06-09T14:27:10.540Z
@BenI. Thanks! I've felt very welcome here. I hope the community continues to grow.
lfalin
CC BY-SA 4.0
2020-06-09T15:51:55.453Z
thanks @Ifalin, but which software tool could help in this process? We used Flex and Bison, but it is a little bit outdated and hard to learn for some students.
Lila
CC BY-SA 4.0
2020-06-09T23:17:10.557Z
@Lila It just comes back to what your goals are. I personally wouldn't use any software to teach Context Free Grammar topics. Remember, Flex and Bison are tools that help you build a parser after you have defined the grammar.
lfalin
CC BY-SA 4.0
2020-06-09T23:27:52.157Z
For courses where I wanted students to have experience building a parser, I would just have them implement one themselves as a finite state machine based around regular expressions. It's much simpler to do that than learning to use Flex and Bison on top of CFG topics.
lfalin
CC BY-SA 4.0
2020-06-08T14:04:25.940Z
2020-06-08T14:04:25.940Z
lfalin
<p>I would like to know if there are some tools to teach the following topics in a programming paradigms course:</p>

<ol>
<li>Demonstration of lexical rules</li>
<li>Demonstration of grammar rules, such as tree parsers of Backus-Naur forms</li>
</ol>

<p>I found that one can teach this topics by using Flex and Bison, but it requires some previous knowledge in C and C++ languages. In any case, are there some alternatives to these tools?</p>

CC BY-SA 4.0
2020-06-08T10:57:48.683Z
You have a misconception. Those tools (and many others) aren't for the _creation_ of lexical or syntactical rules, but for taking already created statements of them in a particular form and automatically creating scanners (from lexical rules) and parsers (from syntactical rules). But the grammars are written with a simple text editor. I actually prefer LL(1) parser tools since they force you to write better languages. I used [CoCo/R](http://www.ssw.uni-linz.ac.at/Coco/) for many years. Grammars _define_ languages. Tools use those definitions to help create actual compilers for them.
Buffy
CC BY-SA 4.0
2020-06-08T11:42:37.440Z
But, what is your course, exactly. Is it an exploration of several existing languages or a discussion of language principles or a compiler building course or ...?
Buffy
CC BY-SA 4.0
2020-06-09T15:50:54.543Z
@Buffy the course is oriented to a discussion of language principles
Lila
CC BY-SA 4.0
2020-06-09T15:53:41.960Z
@Buffy thank you for pointing out that is not really creation, I have modified my question.
Lila
CC BY-SA 4.0
2020-06-12T12:36:57.047Z
Not a tool, but perhaps something you can look at. Eugene Wallingford references a book in this post. The book is available online and will be in print: http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2020-06.html#e2020-06-11T13_02_13.htm
Buffy
CC BY-SA 4.0
2020-06-12T12:42:15.063Z
There is also this (old but still available) book that you probably want to see: https://www.amazon.com/dp/0471597546
Buffy
CC BY-SA 4.0
2020-06-14T17:24:59.370Z
SML (or at least sml/ni, but I imagine it wouldnt be hard to move to, e.g., mlton) has [ml-Ulex/antlr](https://www.smlnj.org/doc/ml-lpt/manual.pdf); similar tools exist for most languages. Plus parser combinators are neat (such as in scala and haskell). But for teaching, dont use the tools.
D. Ben Knoble
CC BY-SA 4.0
2020-06-14T23:09:22.297Z
@Buffy thank you very much, I surely will use that material
Lila
CC BY-SA 4.0
2020-06-15T17:32:24.077Z
Have your students every programmed in a language that wasn't based on or with syntax derived from ALGOL or C? Such as Scheme, say? Have they already programmed in different paradigms, not just the imperative?
Buffy
CC BY-SA 4.0
2020-06-15T17:52:59.157Z
@Buffy, thank you again for your interest. Well in this course, we teach the functional paradigm in Scheme, and previous to that they have also background in OOP, but the later was in Java so maybe it does not count.
Lila
<programming><syntax><programming-paradigms>
Are there any recommended tools for teaching syntax and grammar of programming languages?
# Are there any recommended tools for teaching syntax and grammar of programming languages?

(Asked by: username_0 on 2020-06-08)

I would like to know if there are some tools to teach the following topics in a programming paradigms course:

1. Demonstration of lexical rules
2. Demonstration of grammar rules, such as tree parsers of Backus-Naur forms

I found that one can teach this topics by using Flex and Bison, but it requires some previous knowledge in C and C++ languages. In any case, are there some alternatives to these tools?

**Tags:** programming, syntax, programming-paradigms

> **Comments:**
> **username_1**: You have a misconception. Those tools (and many others) aren't for the _creation_ of lexical or syntactical rules, but for taking already created statements of them in a particular form and automatically creating scanners (from lexical rules) and parsers (from syntactical rules). But the grammars are written with a simple text editor. I actually prefer LL(1) parser tools since they force you to write better languages. I used [CoCo/R](http://www.ssw.uni-linz.ac.at/Coco/) for many years. Grammars _define_ languages. Tools use those definitions to help create actual compilers for them.  
> **username_1**: But, what is your course, exactly. Is it an exploration of several existing languages or a discussion of language principles or a compiler building course or ...?  
> **username_0**: @username_1 the course is oriented to a discussion of language principles  
> **username_0**: @username_1 thank you for pointing out that is not really creation, I have modified my question.  
> **username_1**: Not a tool, but perhaps something you can look at. Eugene Wallingford references a book in this post. The book is available online and will be in print: http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2020-06.html#e2020-06-11T13_02_13.htm  
> **username_1**: There is also this (old but still available) book that you probably want to see: https://www.amazon.com/dp/0471597546  
> **username_2**: SML (or at least sml/ni, but I imagine it wouldnt be hard to move to, e.g., mlton) has [ml-Ulex/antlr](https://www.smlnj.org/doc/ml-lpt/manual.pdf); similar tools exist for most languages. Plus parser combinators are neat (such as in scala and haskell). But for teaching, dont use the tools.  
> **username_0**: @username_1 thank you very much, I surely will use that material  
> **username_1**: Have your students every programmed in a language that wasn't based on or with syntax derived from ALGOL or C? Such as Scheme, say? Have they already programmed in different paradigms, not just the imperative?  
> **username_0**: @username_1, thank you again for your interest. Well in this course, we teach the functional paradigm in Scheme, and previous to that they have also background in OOP, but the later was in Java so maybe it does not count.  

---

## 1 answers

### Answer by username_3 on 2020-06-08. Score: 4

I agree with @username_1's comment. If your goal is to teach the concepts of lexical rules and context-free grammar, I would focus on that rather than on using tools to build parsers from those grammar rules.
I've found that if you have first taught regular expressions and finite automata, that you can teach these concepts quite nicely within that scope using toy languages that you invent and derive in class.
For example, you could create a language defined as:
L = {w | w is a pair of positive integers which are added or subtracted}

For example, these would all be valid strings in such a language: { "3 + 2", "5 - 1", "0 + 2", ... }
Then you could define your grammar by deciding what set of variables (V), set of terminals (Σ), set of substitution rules (R), and start variable (s) you need to describe that language. 
G = (V, Σ, R, s)

This can all be done in a class or group discussion on paper (or whiteboard) without any tools. I find it easiest for students to come up with Σ first, then use that to deduce the members of V, then R, then s.
A guided discussion could go something like:
Σ
"Let's decide what kinds of things we could see in our set of terminals, what symbols (some people refer to these as tokens, though parsers think of these differently) would we see in this language?"
...
"According to our definition of L, this could be any positive integer, a plus, or a minus. So the set Σ could be defined as:"
{ℤ+, +, -}

V
"Now, how could we group these things together?"
...
"The things we're seeing are either positive-integer things, or Operator things, a valid Expression in our language always appears in this form:
Expression -> positive-integer Operator positive-integer

Since the set of things that can be a positive-integer is already represented by ℤ+ in our set of terminals (Σ), that leaves only two types of things in our set of variables:
{ Expression, Operator }

R
"Now, let's come up with the substation rules for this language. We already said that:
Expression -> positive-integer Operator positive-integer

"Since positive-integer is a terminal, we just need a set of rules for Operator. What kinds of things can an Operator be?"
...
Operator -> +
Operator -> -

"So that means the complete set of rules is:"
Expression -> positive-integer Operator positive-integer
Operator -> +
Operator -> -

s
"Now, we just need to decide what the starting variable should be. Which element of V should be our top-level item?"
...
"Expression"
Next Steps
From this point, you can then walk through derivations for the grammar. Depending on where you want to go next, you could then illustrate the grammar as a finite automata or as a parse tree, or express it in Backus-Naur form.
If you still want to discuss parsers, I've also given students assignments where I provide them with a simple grammar definition like the above, and ask them to implement a DFA that can determine if a provided string is a valid expression in the language. This is a lot easier if you've already discussed regular expressions.

> **Comments:**
> **username_4**: Answers like this are why I love this community. You clearly have experience teaching the subject.  Very useful!  
> **username_3**: @BenI. Thanks! I've felt very welcome here. I hope the community continues to grow.  
> **username_0**: thanks @Ifalin, but which software tool could help in this process? We used Flex and Bison, but it is a little bit outdated and hard to learn for some students.  
> **username_3**: @username_0 It just comes back to what your goals are. I personally wouldn't use any software to teach Context Free Grammar topics. Remember, Flex and Bison are tools that help you build a parser after you have defined the grammar.  
> **username_3**: For courses where I wanted students to have experience building a parser, I would just have them implement one themselves as a finite state machine based around regular expressions. It's much simpler to do that than learning to use Flex and Bison on top of CFG topics.  

---

