thebees86 / parser-exercises

Series of autograded ANTLR exercises

Problems

Problem 1

Write a CFG in one.g4 which recognizes all strings with at a substring of three 1 s. The input strings can be of arbitrary length and can have more than three 1 s

Examples:

111

iasdf3h235111

1sges<>a11111a1g120s/ad.sdeae

11111111111111111111111

Problem 2

Write a CFG in two.g4 which recognizes all strings of an odd length.

NOTE: The tests won’t tell you if you are accepting strings with an even number of characters.

Examples:

www

wegni

wawwadageasgnow

w

Problem 3

Write a CFG in three.g4 which recognizes all strings with an even number of the letter X but does NOT accept strings with an odd number of the letter X. The X s don’t have to be adjacent to each other.

NOTE: The tests won’t tell you if you are accepting strings with odd numbers of X. HINT: Regular expressions are your friend here. [^a] is an expression that gives you all letters except a.

Examples:

XX

XAX

XaXXaX

1XengenXnjdnge9qXngr98rn9engeXnsrknkurXX

Problem 4

You are writing software to read a course catalog and you want to recognize anything that looks like a course number - that is, any sequence of 2, 3, or 4 letters, followed by a sequence of 3 numbers where the first digit is 1, 2, or 3. The course number may or may not be followed by a - and a single capital letter or number.

ABC231

CS208

ECON350-A

CHEM100-1

Problem 5

Write a CFG that can recognize simplified syntax for english.

• A sentence consists of a Noun Phrase (NP) followed by a Verb Phrase (VP).
• A noun phrase consists of a determiner (a, the), 0 or more adjectives (funny, silly, angry, green), and a noun (cat, computer, lawyer).
• A verb phrase consists of a verb (ran, meowed, fell) and 0 or more adverbs (quickly, quietly, messily), additional adverbs connected by the word and.

Examples:

The angry lawyer ran messily

The silly computer fell quickly and quietly

A angry green cat meowed

A silly green computer ran quickly

Extension: Can you ensure that words agree with each other? For example, the language above allows “A angry”, but in actual english, we would want to make sure we only accepted “An angry”. How complicated do you think this would make the grammar?