import json
import re
import sys

# Define regular expressions for the tokens
token_patterns = [
    (r'#[^\n]*', None),  # comments (ignored; match till end of line)
    (r'\s+', None),  # whitespace (ignored)
    (r'[', 'LBRACKET'),
    (r']', 'RBRACKET'),
    (r'{', 'LBRACE'),
    (r'}', 'RBRACE'),
    (r'%{', 'LMAPBRACE'),
    (r'=>', 'ARROW'),
    (r',', 'COMMA'),
    (r'(true|false)', 'BOOLEAN'),
    (r'(0|[1-9][0-9_]*)', 'INTEGER'),  # Corrected INTEGER pattern
    (r':[A-Za-z_]\w*', 'ATOM'),  # For :atom syntax
    (r'[A-Za-z_]\w*', 'KEY'),  # For keys in key-value pairs
]

# Create a combined regex pattern for tokenization
regex_parts = [f'(?P<{name}>{pattern})' if name else f'(?:{pattern})' for pattern, name in token_patterns]
token_regex = '|'.join(regex_parts)
token_re = re.compile(token_regex)

class TokenizerException(Exception): pass


class ParserException(Exception): pass


def tokenize(text):
    pos = 0
    while pos < len(text):
        match = token_re.match(text, pos)
        if not match:
            raise TokenizerException(f'Illegal character {text[pos]!r} at index {pos}')
        pos = match.end()
        if match.lastgroup:  # Only yield tokens with a named group (ignore None group names)
            yield match.lastgroup, match.group(match.lastgroup)


# Define a node structure to represent the parse tree
class Node:
    def __init__(self, kind, value):
        self.kind = kind
        self.value = value

    def to_json(self):
        if self.kind == "map":
            return {"%k": self.kind, "%v": {k.to_json()["%v"]: v.to_json() for k, v in self.value}}
        elif self.kind == "list":
            return {"%k": self.kind, "%v": [item.to_json() for item in self.value]}
        else:
            return {"%k": self.kind, "%v": self.value}


class Parser:
    def __init__(self, tokens):
        self.tokens = iter(tokens)
        self.current_token = None
        self.next_token()

    def next_token(self):
        try:
            self.current_token = next(self.tokens)
        except StopIteration:
            self.current_token = None

    def parse(self):
        result = self.parse_sentence()
        if self.current_token is not None:
            raise ParserException('Unexpected token at the end')
        return result

    def parse_sentence(self):
        nodes = []
        while self.current_token is not None:
            node = self.parse_data_literal()
            nodes.append(node)
            if self.current_token and self.current_token[0] in {'COMMA', 'COLON', 'ARROW'}: # Consume any commas or colons between literals
               self.next_token()
        return nodes

    def parse_data_literal(self):
        if self.current_token[0] == 'LBRACKET':
            return self.parse_list()
        elif self.current_token[0] == 'LBRACE':
            return self.parse_tuple()
        elif self.current_token[0] == 'LMAPBRACE':
            return self.parse_map()
        elif self.current_token[0] == 'INTEGER':
            value = int(self.current_token[1])
            self.next_token()
            return Node('int', value)
        elif self.current_token[0] == 'ATOM':
        # Keep the leading colon as required
            value = self.current_token[1]
            self.next_token()
            return Node('atom', value)
        elif self.current_token[0] == 'BOOLEAN':
            value = self.current_token[1] == 'true'
            self.next_token()
            return Node('bool', value)
        elif self.current_token[0] == 'KEY': 
            value = self.current_token[1]
            self.next_token()
            if self.current_token and self.current_token[0] == 'COLON':
               self.next_token()  # Skip ':'
               return Node('key', value)
            return Node('string', value)
        else:
            raise ParserException(f'Unexpected token {self.current_token[1]}')

    def parse_list(self):
        self.next_token()  # Skip '['
        items = []
        while self.current_token and self.current_token[0] != 'RBRACKET':
            item = self.parse_data_literal()
            items.append(item)
            if self.current_token and self.current_token[0] == 'COMMA':
                self.next_token()  # Skip the comma
        if not self.current_token or self.current_token[0] != 'RBRACKET':
            raise ParserException('List not properly terminated with ]')
        self.next_token()  # Skip ']'
        return Node('list', items)

    def parse_tuple(self):
        items = []
        self.next_token()  # Skip '{'
        while self.current_token is not None and self.current_token[0] != 'RBRACE':
            items.append(self.parse_data_literal())
            if self.current_token and self.current_token[0] == 'COMMA':
                self.next_token()  # Skip commas
        if self.current_token is None or self.current_token[0] != 'RBRACE':
            raise ParserException('Tuple not properly terminated with }')
        self.next_token()  # Skip '}'
        return Node('tuple', [item.to_json() for item in items])

    def parse_map(self):
        self.next_token()  # Skip '%{'
        map_items = {}
        while self.current_token and self.current_token[0] != 'RBRACE':
            # Expect a key
            if self.current_token[0] not in {'ATOM', 'KEY'}:
                raise ParserException(f'Expected map key, found {self.current_token}')
            # Extract the key value
            key = self.current_token[1] if self.current_token[0] == 'ATOM' else ':{}'.format(self.current_token[1])
            self.next_token()  # Consume the key
            # Expect '=>' or ':'
            if self.current_token and self.current_token[0] not in {'ARROW', 'COLON'}:
                raise ParserException(f'Expected “=>” or “:”, found {self.current_token}')
            self.next_token()  # Consume '=>' or ':'
            # Parse the value
            value = self.parse_data_literal()
            map_items[key] = value
            if self.current_token and self.current_token[0] == 'COMMA':
                self.next_token()  # Skip comma
        if not self.current_token or self.current_token[0] != 'RBRACE':
            raise ParserException('Map not properly terminated with }')
        self.next_token()  # Skip the '}'
        return Node('map', map_items)

def main():
    try:
        text = input("Enter your input: ")
        # Tokenize the text
        tokens = list(tokenize(text))
        # Check if the tokens list is empty after tokenization
        if not tokens:
            print(json.dumps([]))  # Output an empty list
        else:
            parser = Parser(tokens)
            result = parser.parse()
            # Generate the JSON output from the parse result
            json_output = json.dumps([node.to_json() for node in result], separators=(',', ':'))
            print(json_output)
    except TokenizerException as e:
        sys.stderr.write(str(e) + '\n')
    except ParserException as e:
        sys.stderr.write(str(e) + '\n')


if __name__ == '__main__':
    main()
You are required to submit a zip-archive to gradescope (you can access gradescope from the Tools menu on the brightspace navigation for this course).

Unpacking the archive should result in at least the following files:

prj1-sol/README
prj1-sol/elixir-data.ebnf
prj1-sol/make.sh
prj1-sol/run.sh
The unpacked prj1-sol directory should contain all other source files needed to build and run your project using sh make.sh followed by sh run.sh.

For example, a sample zip file for a project implemented in python contains:

$ unzip -l py/prj1-sol.zip 
Archive:  py/prj1-sol.zip
  Length      Date    Time    Name
---------  ---------- -----   ----
     1127  2024-01-08 03:54   prj1-sol/README
      406  2024-02-10 17:25   prj1-sol/elixir-data.ebnf
     5305  2024-01-08 14:33   prj1-sol/elixir-data.py
      198  2024-01-08 03:54   prj1-sol/make.sh
      242  2024-01-24 20:37   prj1-sol/run.sh
---------                     -------
     7278                     5 files
A do-zip.sh script has been created to facilitate creating the zip file. Please read the comments at the start of the script. A suitable .zipignore has been added to the directory containing the starter files. This .zipignore is suitable for a python or javascript project. If you have used java, then one is available in java-zipignore.

You should verify your zip file before submission. Simply unzip it into a tmp directory:

$ mkdir -p ~/tmp
$ cd ~/tmp
$ unzip PATH_TO_ZIP_FILE  # maybe something like ~/i?44/submit/prj1-sol.zip
This should create a prj1-sol directory in ~/tmp, Go into ~/tmp/prj1-sol and you should be able to successfully run sh make.sh followed by sh run.sh.

When you submit your zip file to gradescope, it will run automated tests:

Verify that all required files have been included.

Build your submission using sh make.sh.

Use your run.sh to Run some tests (note that the actual project grading may use additional tests).

If a step fails, then subsequent steps are aborted. I need to submit the code written using the instructions above. tell me how to do it.