Nick Says

This week, I added the finishing touches to the little SQL parser I was working on last week. I wrote a simple LL parser with left-recursive rules that can handle nested SQL queries. Using tokens produced by the SLY lexer, the parser starts with the term of highest complexity (in this case, Query) and breaks it down into it's smallest, atomic components, forming a top down parse tree. In this example, the parse tree is returned as a list.

Output:

hypatia@Yours-MacBook-Air:https://cs.marlboro.college/cours/spring2019/jims_tutorials/Documents/programming-languages$ python3 sqllexer.py 
(SQL)>> SELECT name FROM classlist WHERE age IN ( SELECT age FROM roster WHERE id = 3 )
['QUERY', 'Attribute', 'name', 'FROM', 'Relation', 'classlist', 'WHERE', 'Attribute', 'age', 'IN', 'LPAREN', 'QUERY', 'Attribute', 'age', 'FROM', 'Relation', 'roster', 'WHERE', 'Attribute', 'id', 'ASSIGN', 'NUMBER', '3', 'RPAREN']

The parser returns the parse tree as a list, which always breaks down from largest to smallest term. So, if the list above was made into a graph (this is actually an annotated parse tree rather than a parse tree since it features the values of each attribute):

                         _____QUERY____
                        /      |       \
                  SELECT      FROM    WHERE
                      /        |          \
              Attribute    Relation       _IN__
                    /          |         /     \
                  name    classlist    age   ___QUERY___
                                            /     |     \
                                          SELECT  FROM   WHERE
                                          /       |       \
                                     Attribute  Relation  ASSIGN (=)
                                        /          |        /     \
                                      age         roster  id       3

I also started reading about semantic analysis: from what I understand, the big tasks that are completed during semantic analysis involve determining the scope and type of variables and attributes to ensure that the compiled program actually produces the expected value/result. There are some languages which are dynamically scoped which makes this problem a bit more difficult, but most happen to be statically scoped, which means that their scope is not changed during runtime. I found a lot of good information in this powerpoint presentation

attachments

		last modified	size
	sqllexer.py	Sun Apr 28 2024 03:15 pm	6.4K