4

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses just like the text books I have.

My question is about language recognisers verses generators.

I get the overriding principle of a recogniser. That it analyses a language and is able to determine nay or yay if a String belongs to a language. This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyser (which I assume to be recognisers) do not just say yes or no, they also say where don't they...?

However, language generators. No one seems to be very clear about what they are. The typical description I get is For example Sebasta's Concepts of Programming Languages says 'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.' Seriously? That's it?? Your kidding right....

I read that Regex is an example of a Generator, then why when people talk of generators do they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.

Can someone provide for me a clearer distinction of what a recognizer is?

Improve this question
1

2 Answers 2

Reset to default
2

I'm surprised you didn't find your answer in Sebesta's Concepts of Programming Languages... In short:

Recogniser: sentences -> grammar. Application: to check if given sentences are part of the language grammar. This is an essential part of a compiler or interpreter.

Generator: grammar -> sentences. Application: to provide examples of valid sentences in the language. This is an essential part of a programming language manual.

For instance, the user manual for a certain programming language may explain in words what a valid assignment looks like, and even provide a BNF rule (something like: assign -> var = expr), but it will also include examples of valid assignments so that the programmer understands better (e.g., a = b or x = y + 2*z). Such examples are generated from the BNF through a process known as derivation.

Improve this answer
3
  • I did find Sebesta's discripton at the beginning of chapter 3 is very misleading. As I mentioned Sebester said "'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed" Why did he not just say something about grammars. It's not a great way to write a chapter introduction if I'm honest. Your description of a grammar is spot on. I only figured this out once I'd gotten two thirds of the way though chapter three.
    – Andrew S
    Apr 2, 2014 at 8:07
  • Thanks. I agree with you that, while Sebesta's is a good textbook overall, at times it could be clearer -- and esp. since it is aimed at undergrads who are by definition new to most concepts in the book... (BTW if anyone knows of a better PL textbook, I'm interested :)
    – michl
    Apr 2, 2014 at 17:49
  • Recogniser: sentences -> grammar should be: Recogniser: sentences x grammar -> true/false.
    – reinierpost
    Sep 6, 2016 at 11:40
1

First off, these are not difficult subjects in their general sense, so do not be surprised that generating sentences of a language is it.

There is one concept shared by both a language recognizer, as well as a language generator, and that is a language.

Languages can be defined as simple as L = {a, b, c} where the language L only knows three words/sentences. Regular expressions themselves are neither recognizers nor generators. Instead, a regular expression is a way of defining a language. For example, the regular expression a+ defines the language L' = {a, aa, aaa, aaaa, ... }.

Now if you look into those textbooks of yours, I am sure, there is a section on how to convert a regular expression into a (non-)deterministic finite automaton. Such an automaton is now a language recognizer, that fails to accept a b, but does accept aaa when constructed from the regular expression a+.

On the other hand, a language generator is something that will output one element of L' at a time, eventually, generating all of L'. For example, a generator for L' could give you aaa, then a, then aa, then aaaa, and so on.

Generally, languages are infinitely large, hence, generators need to generate an infinite number of sentences in that language. Consider the language L1 defined by the regular expression a+b+. If you have a generator that outputs ab, aab, aaab, ..., then it can run infinitely long, but you will never ever see a word that has more than one b. Such generators tend to be rather useless due to their biased nature.

Therefore, to reduce the "that's it" effect, we typically demand from a generator, that given any word from the language, the generator eventually produces it. So you could pick aabb and your generator must have a finite number of steps that it needs to produce that word. It cannot just infinitely increase the number of as anymore.

Now, to start making things really complicated, assume a more interesting language like, for example, Java. When you have a Java language generator, then this thing will eventually produce all of the Java classes that you have written and will ever write in your life as a Java programmer. I leave it as an exercise to you to think about how to realize such a thing - and do not forget: only valid Java programs are allowed. It must not output gibberish, but only sentences of the language.

Usage of language generators is primarily in CS theory. For practical purposes their infinite nature makes any kind of meaningful usage rather problematic. Apart from pathological cases, where the language is trivial and finite, one could use these generators for testing tools that are supposed to process sentences of the language. For example, you could test a Java parser against a Java generator by having it continuously parse the generated progarms.

Improve this answer
4
  • So going by your description at the end, what use are language generators, if their aim is to eventually produce all possible expressions of a language?
    – Andrew S
    Mar 5, 2014 at 6:23
  • "but you will never ever see a word that has more than one b" this is not true. Instead of going with a DFS over the graph you go with a BFS.
    – vz0
    Jan 27, 2015 at 9:39
  • That's why I specifically described the generator as a DFS-generator. I did not say that you will never see a generator for that. Instead, I was even explaining why a BFS-like approach is preferred in the very next paragraph, so please read more carefully before making such a claim.
    – Frank
    Jan 27, 2015 at 12:08
  • what use are language generators Well, let's say you have five nodes in a database cluster, named ^dbnode[1-5]$. That regex can be used to both recognize a use of a database node name, and to generate the list of database node names. Anytime you'd write a for loop or a while loop over a generated list, you can think of that list as the output of a generator. You can generate the full list of integers, for example, using a generator expression.
    – Parthian Shot
    May 14, 2018 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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