2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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 for many years. Grammars define languages. Tools use those definitions to help create actual compilers for them. $\endgroup$ – Buffy Jun 8 at 10:57
  • $\begingroup$ 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 ...? $\endgroup$ – Buffy Jun 8 at 11:42
  • $\begingroup$ @Buffy the course is oriented to a discussion of language principles $\endgroup$ – Lila Jun 9 at 15:50
  • $\begingroup$ @Buffy thank you for pointing out that is not really creation, I have modified my question. $\endgroup$ – Lila Jun 9 at 15:53
  • 1
    $\begingroup$ 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: cs.uni.edu/~wallingf/blog/archives/monthly/… $\endgroup$ – Buffy Jun 12 at 12:36
3
$\begingroup$

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.

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Answers like this are why I love this community. You clearly have experience teaching the subject. Very useful! $\endgroup$ – Ben I. Jun 8 at 21:53
  • $\begingroup$ @BenI. Thanks! I've felt very welcome here. I hope the community continues to grow. $\endgroup$ – lfalin Jun 9 at 14:27
  • $\begingroup$ 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. $\endgroup$ – Lila Jun 9 at 15:51
  • $\begingroup$ @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. $\endgroup$ – lfalin Jun 9 at 23:17
  • $\begingroup$ 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. $\endgroup$ – lfalin Jun 9 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.