Questions tagged [grammars]

For challenges pertaining to a formal grammar often a context free grammar.

Filter by
Sorted by
Tagged with
4
votes
3answers
185 views

Print valid arithmetic expressions

Recursively define a "valid arithmetic expression": Any natural number is a valid arithmetic expression. If s is a valid arithmetic expression, then so is ...
9
votes
5answers
643 views

Abstract Rewriting Challenge (Robbers)

This is a somewhat proof-golf-like cops-and-robbers challenge. This is the robbers' thread; the cops' thread is here. Robbers The cops will post abstract rewriting systems. Your task is to crack ...
27
votes
10answers
950 views

Abstract Rewriting Challenge (Cops)

This is a somewhat proof-golf-like cops-and-robbers challenge. This is the cops' thread; the robbers' thread is here. Cops Your task is to define an abstract rewriting system in which the ...
3
votes
2answers
262 views

My program knows your language. Does yours?

Given a list of production rules and start symbol of a proper finite context-free grammar (CFG) of printable characters, your program or function must output its formal language (the set of all ...
11
votes
5answers
585 views

Computers will never taste a refreshing cookie

Inspired by github.com/JackToaster/Reassuring-Parable-Generator, in turn inspired by xkcd.com/1263. The possible words are derived from the reassuring.cfg of that repository. Having a look at the ...
10
votes
0answers
404 views

Please parse this aLL1en language

Background Due to some unfortunate accident during coding you are now teleported and stranded on an alien planet. You really hope that the locals will be helpful and point to the general direction of ...
14
votes
1answer
374 views

Find the follow sets

The challenge below requires you to be familiar with formal parser theory. If you don't know what the question is asking because you don't know what the terms mean, context-free grammars and first/...
0
votes
3answers
237 views

Create a Question Asker! [closed]

Writing questions for programming puzzles is tiring and takes many minutes to do. This is where you come in. Your job is to write a program that randomly generates plausible-sounding (but not ...
9
votes
2answers
668 views

Compress data with context free grammars

It is possible to compress some kinds of data, such as human text or source code, with straight-line grammars. You basically create a grammar whose language has exactly one word – the uncompressed ...
7
votes
1answer
375 views

Write a CFG acceptor

Write a program that, given a context free grammar and a string, returns whether the string is a word of the language defined by the grammar. Input Your program should read a context free grammar ...
8
votes
1answer
1k views

Random Sentence Generator

Write the shortest program you can in any language that reads a context-free grammar from and the number of sentences to produce from stdin, and generates that many ...