Programming Languages 1 MIDTERM

Lexical analysis

This involves reading the source code character from left to right and organizing them into tokens.

It eliminates comments and whitespace within the source code.

tokens

Lexical Analysis aims to read the input code and break it into meaningful elements called _______ for a computer to understand easily.

Lexical analyzer

collects characters into logical groupings and assigns internal codes to the groupings based on their structure.

lexemes

These logical groupings of lexical analyzer is called _______

tokens

the internal codes for categories of these groupings are the ____

regular expressions

In programming language, tokens can be described using ________

Deterministic Finite Automaton (DFA)

A lexical analyzer uses a __________ to recognize these tokens, as they can identify regular languages.

Input Preprocessing

Involves cleaning up the input text and preparing it for lexical analysis.

This covers the removal of comments, whitespaces, and other non-essential characters from the input text.

Tokenization

Involves the process of breaking the input text into a sequence of tokens.

This is done by matching the characters in the input text against a set of patterns or regular expressions that define the different types of tokens.

Token Classification

The analyzer determines the type of each token.

For instance, the analyzer might classify the keywords, identifiers, operators, and punctuation symbols as separate token types.

Token Validation

The analyzer checks if each token is valid based on the rules of the programming language.

For instance, the analyzer might check that a variable name is a valid identifier or that an operator has the correct syntax.

Output Generation

The analyzer generates the output of the lexical analysis process, typically a list or sequence of tokens (token stream).

The list of tokens can then be passed to the next stage of compilation or interpretation, which will be sent to the parser for syntax analysis.

TOKENS

_______can be individual words or symbols in a sentence, such as keywords, variable names, numbers, and punctuation.

Alphabets

All the numbers and alphabets are considered hexadecimal alphabets by language.

Strings

The collection of different alphabets occurring continuously

string length

The _____ is defined by the number of characters or alphabets occurring together.

For example, the length of |STIisthebest| is 12 since there are 12 characters.

Symbols

High-level programming languages contain special symbol

Non-tokens

Comments, preprocessor directive, macros, blanks, tabs, newlines.

LEXEMES

____ are the sequence of characters matched by a pattern to form the token or a sequence of input characters that comprises a single token.

Syntax analysis, or parsing

Is the process of analyzing a string of symbols according to the rules of formal grammar.

It checks the source code to ensure that it follows the correct syntax of the programming language it is written.

Syntax errors

are identified and flagged in this phase and must be corrected before the program can be successfully compiled.

Parse tree or Abstract Syntax Tree (AST)

A _______ is the output of this phase, representing the program’s structure.

context-free grammar (CFG)

Syntax analysis uses ____ to define the syntax rules of a programming language.

They include production rules that describe how valid strings (token streams) are formed.

This also specify the grammar of a language to ensure that the source code adheres to the language’s syntax.

Parsing

The tokens are analyzed based on the grammar rules of the programming language.

A parse tree or AST is constructed to represent the hierarchical structure of the program.

Error Handling

If the input program contains syntax errors, the syntax analyzer detects and flags them to the user, indicating where the error occurred.

Symbol Table Creation

The syntax analyzer creates a symbol table, a data structure that stores information about the identifiers used in the program, such as type, scope, and location.

Derivation

It is the process of applying the rules of Context-Free Grammar to generate a sequence of tokens to form a valid structure.

Simply, it is a sequence of production rules to get the input string for the parser.

left-most derivation

It is called _____ if the sentential form of an input is scanned and replaced from left to right.

left-sentential form

What do you call to the derived sentimental form of left-most deriverasion

right-most derivation

It is called the _____ if the input is scanned and replaced with production rules

right-sentential form

What do you call to the derived sentimental form of right-most deriverasion

Parse Tree

It is the graphical representation of a derivation. It is convenient to see how strings are derived from the start symbol, which becomes the root of the parse tree.

Ambiguity

The grammar is ambiguous if it has more than one parse tree, either left or right derivation, for at least one (1) string.

inherently ambiguous

The language generated by ambiguous grammar is _______. No method can detect and remove ambiguity automatically.

Still, it can be removed by either re-writing the whole grammar without ambiguity or by setting and following associativity and precedence constraints. These methods decrease the chances of ambiguity in a language or its grammar.

Associativity

When an operand has operators on both sides, the side on which the operator takes this operand is decided by the association of those operators.

Left-associative operations

include Addition, Multiplication, Subtraction, and Division.

For example: id op id op id will be evaluated as (id op id) op id

Simply, 2 + 3 + 4 will be evaluated as (2 + 3) + 4

Right-associative operations

such as exponentiation will have the following evaluation in the same expression.

For example: id op id op id will be evaluated as id op (id op id) Simply, 2 ^ 3 ^ 4 will be evaluated as 2 ^ (3 ^ 4)

Precedence

When two (2) different operators share a common operand, the precedence of operators decides which will take the operand

hierarchy of priorities

In Python, some operators are performed before others. It is called the __________