Authors: Aniketh Aatipamula, Nabeel Ahmad, Omar Mohammed
Introduction
Our language aims to provide a definitive structure to ordering at the colloquially named “bowl-slop” class of fast-casual restaurants. Bowl-slop restaurants can be defined as any restaurant where you can order a bowl/wrap/sandwich that you build on your own as the options are displayed in front of you. The language should be able to generate and accept all the possible combinations of ingredients that are typically found in bowl-slop restaurants. For example the language accepts an ordered list of ingredients such as, “bowl, rice, chicken, lettuce, tomatoes, olives, white sauce”. Due to the fact that our language contains rules which require separation from other rules, we chose to use a CFG and PDA to represent our language. The rules should be right-recursive and build the ordering list from left-to-right.
The language closely follows the ordering structure of these bowl slop restaurants. The alphabet consists of all the basic ingredients commonly used in bowl-slop restaurants. This includes bowl, wrap, sandwich, rice, noodle, tortilla, pita, sub, bun, slice bread, toasted, chicken, beef, seafood, pork, lamb, turkey, veggie, spicy sauce, vinaigrette, mayo, pesto, marinara, white sauce, garlic sauce, lettuce, spinach, tomato, olives, onions, peppers, pickles, mushroom, beans, avocado, cheese. We then define rules for picking some base meal and branch from there creating different rules for each specific case. We start with either a bowl, wrap, or sub, each have their own specific carbs and subsequently proteins that can be used. Veggies, and sauces can also be added in this fashion but can recurse in order to add any number of veggies and sauces, as mostly allowed by many bowl-slop restaurants.
Expanding on this, our bowl-slop language could add other items that are typically available on bowl-slop menus across the globe. Side dishes like chips, fries, falafel, and drinks could be added to supplement the main dish being purchased. This language provides an ordered and adaptable method of ordering in a bowl-slop restaurant. There are clear rules for the ordering method, where the customer orders from either a bowl/wrap/sandwich and customizes that selection to their preference. This approach, although complex in its conception, is a universally simple approach that also ensures accuracy and satisfaction for the customer.
Grammar
Alphabet:
Context Free Grammar:
S → bowl A | wrap B | sandwich C
A → rice D | noodle D | D
B → tortilla E | pita E
C → bun G | bread G | sub G
D → chicken D | beef D | seafood D | pork D | H | λ
E → chicken E | beef E | pork E | lamb E | H | λ
F → chicken F | beef F | pork F | turkey F | H | λ
G → toasted F | F
H → lettuce H | spinach H | tomato H | onions H | olives H | peppers H | pickles H | mushroom H | beans H | avocado H | cheese H | I
I → hot I | vinaigrette I | mayonnaise I | pesto I | marinara I | white I | garlic I | λ
Automata
PDA:
digraph {
rankdir=LR;
S [shape=circle];
q1 [shape=circle];
q2 [shape=circle];
q3 [shape=circle];
q4 [shape=circle];
q5 [shape=circle];
q6 [shape=doublecircle];
S -> q1 [label="bowl, λ ➝ A
wrap, λ ➝ B
sandwich, λ ➝ C"];
q1 -> q2 [label="noodle, A ➝ D
rice, A ➝ D
λ, A ➝ D "];
q1 -> q3 [label="tortilla, B ➝ E
pita, B ➝ E"];
q1 -> q4 [label="bun, C ➝ G
bread, C ➝ G
sub, C ➝ G"];
q2 -> q6 [label="chicken, D ➝ λ
beef, D ➝ λ
seafood, D ➝ λ
pork, D ➝ λ
λ, D ➝ λ"];
q3 -> q6 [label="chicken, E ➝ λ
beef, E ➝ λ
pork, E ➝ λ
lamb, E ➝ λ
λ, E ➝ λ"];
q4 -> q5 [label="toasted, G ➝ F
λ, G ➝ F"];
q5 -> q6 [label="chicken, F ➝ λ
beef, F ➝ λ
pork, F ➝ λ
turkey, F ➝ λ
λ, F ➝ λ"];
q6:n -> q6 [label="lettuce, λ ➝ λ
spinach, λ ➝ λ
tomatoes, λ ➝ λ
onions, λ ➝ λ
olives, λ ➝ λ
peppers, λ ➝ λ
pickles, λ ➝ λ
mushrooms, λ ➝ λ
beans, λ ➝ λ
avocado, λ ➝ λ
cheese, λ ➝ λ
hot, λ ➝ λ
vinaigrette, λ ➝ λ
mayonnaise, λ ➝ λ
pesto, λ ➝ λ
marinara, λ ➝ λ
white, λ ➝ λ
garlic, λ ➝ λ
λ, λ ➝ λ"];
}
Data Structure
Our data structure represents a PDA in a plaintext file format. The first line contains all possible states in the PDA. The second line contains all possible symbols in the alphabet. The third line contains the start state and fourth line contains all the final state(s).
In Python the data structure is represented as a dictionary of tuples.
PDA = Dict[Tuple[str, str], Tuple[str, str, str]]
The key tuple contains two string values. The first value in the tuple is the current state, the second value is the symbol read. The value tuple contains three string values. The first value in this tuple is the stack symbol to pop. The second value in the tuple is the stack symbol to push. The third value in the next state to transition into.
S q0 q1 q2 q3 q4 q5 q6
lambda bowl wrap sandwich rice noodle tortilla pita sub bun bread toasted chicken beef seafood pork lamb turkey veggie hot vinaigrette mayonnaise pesto marinara white garlic lettuce spinach tomatoes olives onions peppers pickles mushrooms beans avocado cheese
S
q6
S bowl lambda A q1
S wrap lambda B q1
S sandwich lambda C q1
q1 noodle A D q2
q1 rice A D q2
q1 lambda A D q2
q1 pita B E q3
q1 tortilla B E q3
q1 bread C G q4
q1 bun C G q4
q1 bread C G q4
q2 chicken D lambda q6
q2 beef D lambda q6
q2 seafood D lambda q6
q2 pork D lambda q6
q2 lambda D lambda q6
q3 chicken E lambda q6
q3 beef E lambda q6
q3 pork E lambda q6
q3 lamb E lambda q6
q3 lambda E lambda q6
q4 toasted G F q5
q4 lambda G F q5
q5 chicken F lambda q6
q5 beef F lambda q6
q5 pork F lambda q6
q5 turkey F lambda q6
q5 lambda F lambda q6
q6 lettuce lambda lambda q6
q6 spinach lambda lambda q6
q6 tomatoes lambda lambda q6
q6 onions lambda lambda q6
q6 olives lambda lambda q6
q6 peppers lambda lambda q6
q6 pickles lambda lambda q6
q6 mushrooms lambda lambda q6
q6 beans lambda lambda q6
q6 avocado lambda lambda q6
q6 cheese lambda lambda q6
q6 hot lambda lambda q6
q6 vinaigrette lambda lambda q6
q6 mayonnaise lambda lambda q6
q6 pesto lambda lambda q6
q6 marinara lambda lambda q6
q6 white lambda lambda q6
q6 garlic lambda lambda q6
q6 lambda lambda lambda q6
Testing
Code
This implementation in Python has two classes, one for the stack of the PDA and one for the PDA itself. The PDA stores information about the automata and all the transitions and can be built from a data structure file formatted as previously shown.
There is one function called check which given a white space separated string of "characters" will return whether or not the string is valid in our language.
Finally there are a couple of helper helper functions and two main functions. test makes sure the PDA is valid for our test cases while main starts an interactive REPL that will accept or reject any string.
The traceback output is a list of tuples with three values. The start state, the current character, and the state to transition to on the next iteration. For example (q1, bowl, q2) reads as "The automata started in state q1, read character "bowl" and is going to state q2.
The code can be run with the following commands:
python3 version >=3.9 must be installed. The data.txt file must exist next to final.py.
# Get the code
git checkout https://github.com/aaatipamula/bowl-slop.git
# Change directories to the source code directory
cd bowl-slop
# Run the code
python3 final.py
The debug flag can be added when running final.py to show a live and more detailed output. This will show the traceback for rejected strings as well.
python3 final.py debug
import sys
from typing import Dict, Iterable, List, Tuple
PDAMap = Dict[Tuple[str, str], Tuple[str, str, str]]
CheckReturn = Tuple[bool, List[Tuple[str, str, str]]]
class Stack(list):
def __init__(self) -> None:
self.push = self.append
def pops(self, expect: str):
if self.pop() != expect:
raise RuntimeError("Invalid stack symbol removed")
class PDA:
def __init__(
self,
states: List[str],
alphabet: List[str],
start_state: str,
final_states: List[str]
) -> None:
self.states = states
self.alphabet = alphabet
self.start_state = start_state
self.final_states = final_states
self.map: PDAMap = {}
@classmethod
def from_file(cls, file: str):
with open(file, "r") as f:
states = f.readline().strip().split()
alphabet = f.readline().strip().split()
start_state = f.readline().strip()
final_states = f.readline().strip().split()
pda = cls(states, alphabet, start_state, final_states)
map = {}
try:
for line in f:
if line in ("\n", ""): continue
f, r, pop, push, t = line.strip().split()
map[(f, r)] = (pop, push, t)
except ValueError:
print("Invalid file format")
exit(1)
pda.map = map
return pda
def check(self, input: str, *, debug: bool = False) -> CheckReturn:
stack = Stack()
curr_state = self.start_state
characters = input.strip().split()
traceback = []
while len(characters) > 0 and curr_state not in self.final_states:
character = characters.pop(0)
if character not in self.alphabet:
return False, traceback
next = self.map.get((curr_state, character))
if next is None:
next = self.map.get((curr_state, "lambda"))
characters.insert(0, character)
if next is None:
return False, traceback
pop, push, next_state = next # Unpack values
try:
if pop != "lambda": stack.pops(pop)
if push != "lambda": stack.push(push)
except Exception:
return False, traceback
if debug: print((curr_state, character, next_state), stack, characters)
traceback.append((curr_state, character, next_state))
curr_state = next_state
while self.map.get((curr_state, "lambda")) and curr_state not in self.final_states:
next = self.map.get((curr_state, "lambda"))
if next is None:
return False, traceback
pop, push, next_state = next # Unpack values
try:
if pop != "lambda": stack.pops(pop)
if push != "lambda": stack.push(push)
except Exception:
return False, traceback
if debug: print((curr_state, "lambda", next_state), stack, characters)
traceback.append((curr_state, "lambda", next_state))
curr_state = next_state
while len(characters) > 0:
character = characters.pop(0)
if character not in self.alphabet:
return False, traceback
next = self.map.get((curr_state, character))
if next is None:
characters.insert(0, character)
break
pop, push, next_state = next # Unpack values
try:
if pop != "lambda": stack.pops(pop)
if push != "lambda": stack.push(push)
except Exception:
return False, traceback
if debug: print((curr_state, character, next_state), stack, characters)
traceback.append((curr_state, character, next_state))
accepted = len(stack) == 0 \
and curr_state in self.final_states \
and len(characters) == 0
return accepted, traceback
def printl(o: Iterable):
for v in o:
print(v)
def test():
pda = PDA.from_file("./data.txt")
tests = [
("bowl", True),
("bowl bowl", False),
("bowl chicken", True),
("bowl chicken chicken", False),
("bowl rice chicken", True),
("bowl rice chicken lettuce beans white", True),
("bowl noodle beef marinara", True),
("sandwich", False),
("sandwich bun", True),
("sandwich beef", False),
("sandwich bread beef", True),
("sandwich bread turkey mayonnaise cheese", True),
("sandwich sub toasted beef onions cheese", True),
("wrap", False),
("wrap tortilla", True),
("wrap lamb", False),
("wrap pita lamb", True),
("wrap tortilla chicken", True),
("wrap tortilla beef lettuce cheese hot avocado", True),
]
for test, expected in tests:
accepted, _ = pda.check(test)
try:
assert accepted == expected
except AssertionError:
print(f"Expected ({expected}) got ({accepted}) for:\n{test}\n")
def main():
pda = PDA.from_file("./data.txt")
debug = False
if len(sys.argv) > 1:
debug = sys.argv[1].lower() == "debug"
while True:
user_string = input("> ")
if user_string.lower() == "exit": break
accepted, traceback = pda.check(user_string, debug=debug)
if accepted:
print("accepted")
printl(traceback)
else:
print("rejected")
if __name__ == "__main__":
test()
main()