"People are saying that language is not really that significant.

As long as I can deliver my thoughts to the person I speak with, I think it's just enough.

Language won't be that significant unless I'm going to travel overseas, which not gonna happen soon."

And so what my inner self said.

DUARR TBFO SEASON 2

Here we were told to make a parser.

Yeah, a parser.

A frickin' parser.

With focus on the usage of Context-Free Grammar and CYK Algorithm.

No external libraries or packages that are allowed to be used or downloaded, so it's all about me, you, and the programming language's standard library.

Good thing that it allows us to freely choose any programming language we want.

Ahem..

So, our goal right now is to construct a parser that can verify whether our Python code is "in the language" or not. That is to say, we are going to construct a program that will give us two outputs when we feed it a bunch of string.

Is it a genuine and "grammarly-correct" python code or nay?

So, there are two steps when making a parser.

Make a lexer
Make your grammar

"But hold down, what the heck is lexer?"

Well, I'm going to assume that you who read this already know what the heck is Context-Free Grammar, how they works, yada yada yada.

Lexer, and why you need it.

In CFG, a grammar can be described using a set of 4-tuples, which I'm not going to cover, and represented in the form of production of variables and terminals.

For example :

S -> A B C

A -> 'F'

B -> B B

B -> 'U'

C -> 'N'

is a grammar that can accept a string 'FUN' with the number of letter 'U' can be more than one.

As long as the alphabet we test are exists in the language definition, everything should be fine.

But how about a programming language?

Lets see two examples of a "from-import-as" declaration in python

from scikit import tfidvectorizer as tfid

============================

from a import b as c

Both lines are valid in python, but "scikit", "tfidvectorizer", "a", .... are arbitrary. You can basically use any terms, any words, and combination of characters you want, and it still a valid term in python.

So, you need a way in order to generalize those into one single term. That's where lexer comes in.

Lexer, or lexical analyzer, or often called tokenizer, is a program that can convert those arbitrary terms into a term that falls under the category, where the category is already defined.

Well

What it says is that "hey, this 'scikit' and 'tfidvectorizer' is something that relates to object or variable or properties right? Well, I'm just going to call it 'identifier', okay?"

So, the former sentence :

from scikit import tfidvectorizer as tfid

============================

from a import b as c

is going to be converted into

from object import object as object

============================

from object import object as object

This way, things are a lot less random, because we already generalizing the terms. Now we can feed this sentence into the parser.

Parser, and why you need to put effort on it.

Now that we have our input string generalized by the lexer, now it's time for us to check whether it's a valid string or not, that is to say, whether the string is in the grammar or nay.

Let's define from-import-as grammar

S -> FROM OBJECT IMPORT OBJECT AS OBJECT

FROM -> 'from'

OBJECT -> 'object'

IMPORT -> 'import'

AS -> 'as'

This is a basic from-import-as grammar that can accept any sentence as long as it's in the form of 'from object import object as object'. But the grammar is not just that.

In python, the "from object" part and "as object" part can be taken away, so you can have sentences

from a import b as c

from a import b

import b

import b as c

and all are a valid python line. So, you'll need to modify your grammar into something that fits all the cases, as defined in the python standard.

S -> FROM OBJECT IMPORT OBJECT AS OBJECT

S -> FROM OBJECT IMPORT OBJECT

S -> IMPORT OBJECT

S -> IMPORT OBJECT AS OBJECT

FROM -> 'from'

OBJECT -> 'object'

IMPORT -> 'import'

AS -> 'as'

That way, we can handle all the possible case regarding the from-import-as grammar.

Heck yes, we have defined our grammar, the next thing to do is to actually make the parser. A parser accepts grammar and string, where the grammar is a CFG, and the string is anything as long as the element/alphabet/words are defined inside the CFG.

We're told to use CYK algorithm, which is an algorithm to check if our string is in the language. But the downside of using CYK algorithm is that the grammar needs to be in CNF, namely Chomsky Normal Form.

To put it simple, CNF means that one variable production can only produce maximum 2 variables.

So, putting that in mind, convert the grammar above to CNF, and let's step for the actual parser.

You can construct your CYK algorithm using the definition you can find in wikipedia, or using the existing algorithm made by others. I'm using this one

On the other hand, the lexer I'm using is this one. This lexer is regex-based, so you need prior knowledge in using regular expressions and how they work.

Building things up

==ON CONSTRUCTION==

tl;dr;

Put the text you want to test in input_file.txt
Put the grammar in grammar.txt
Include cyk_parser in lexer.py
Make a variable to contain the tokenized output from the lexer
Call the parser with the variable you've made before as one of the parameter.

Me, Python, and Context-Free Grammar