ALGORITHM SUBSTRING
Step 1: Start
Step 2: Define the following lexical rules:
Step 2.1: Rule 1: If the input word contains the substring "abc", replace it with "ABC" and
print the modified word.
Step 2.2: Rule 2: If the input contains spaces or tabs, ignore them (do nothing).
Step 2.3: Rule 3: If the input contains any other characters (symbols, numbers, etc.), print
them as they are.
Step 2.4: Rule 4: If a newline is encountered, print the newline.
Step 3: Call the yylex() function to begin scanning the input.
Step 4: Read the input token by token.
Step 5: Check if the token matches any of the defined rules.
Step 6: Apply the corresponding rule and output the result.
Step 7: Repeat the process until the end of input is reached.
Step 8: Stop.
ALGORITHM TOP DOWN PARSER.
Step 1: Start
Step 2: Input the expression
Step 2.1: Prompt the user to enter an arithmetic expression
Step 2.2: Store the input string in the array input[]
Step 2.3: Initialize pos = 0 and set current = input[pos]
Step 3: Define helper functions
Step 3.1: advance() – increment pos and set current = input[pos]
Step 3.2: match(expected) – if current == expected, call advance(), else call error()
Step 3.3: error() – print syntax error with position and terminate the program
Step 4: Define parsing functions according to grammar
Step 4.1: E() – parse Expression
Step 4.1.1: Call T()
Step 4.1.2: Call Eprime()
Step 4.2: Eprime() – parse Expression Prime
Step 4.2.1: If current == '+'
Step [Link]: Call match('+')
Step [Link]: Call T()
Step [Link]: Call Eprime() recursively
Step 4.3: T() – parse Term
Step 4.3.1: Call F()
Step 4.3.2: Call Tprime()
Step 4.4: Tprime() – parse Term Prime
Step 4.4.1: If current == '*'
Step [Link]: Call match('*')
Step [Link]: Call F()
Step [Link]: Call Tprime() recursively
Step 4.5: F() – parse Factor
Step 4.5.1: If current == '('
Step [Link]: Call match('(')
Step [Link]: Call E()
Step [Link]: Call match(')')
Step 4.5.2: Else if current is an alphanumeric character
Step [Link]: Call match(current)
Step 4.5.3: Else call error()
Step 5: Start parsing
Step 5.1: Call E() to begin parsing the expression
Step 6: Check for completion
Step 6.1: If current == '\0', print "Input string is valid."
Step 6.2: Else, print "Syntax Error: Unexpected symbol 'current'"
Step 7: Stop
ALGORITHM BOTTOM UP PARSER.
Step 1: Start
Step 2: Input the expression
Step 2.1: Prompt the user to enter the input string (use 'id' for identifiers)
Step 2.2: Store the input in the array input[]
Step 2.3: Initialize top = -1 for stack and i = 0 for input index
Step 3: Define stack operations
Step 3.1: push(c) – increment top and store character c on top of stack
Step 3.2: pop() – decrement top
Step 4: Define reduce() function to apply grammar rules
Step 4.1: Repeat reduction until no more rules can be applied
Step 4.2: If top >= 1 and top two symbols are 'i','d'
Step 4.2.1: Replace 'id' with 'E' on stack
Step 4.2.2: Print "Reduce: E -> id"
Step 4.3: If top >= 2 and top three symbols are 'E','+','E'
Step 4.3.1: Replace 'E+E' with 'E' on stack
Step 4.3.2: Print "Reduce: E -> E+E"
Step 4.4: If top >= 2 and top three symbols are 'E','','E'
Step 4.4.1: Replace 'EE' with 'E' on stack
Step 4.4.2: Print "Reduce: E -> E*E"
Step 4.5: If top >= 2 and top three symbols are '(', 'E', ')'
Step 4.5.1: Replace '(E)' with 'E' on stack
Step 4.5.2: Print "Reduce: E -> (E)"
Step 4.6: Else, break
Step 5: Start parsing input
Step 5.1: Print table header "Stack", "Input", "Action"
Step 5.2: While input[i] != '\0'
Step 5.2.1: If input[i] == 'i' and input[i+1] == 'd'
Step [Link]: Push 'i' and 'd' onto stack
Step [Link]: Increment i by 2
Step [Link]: Print stack, remaining input, and "Shift id"
Step 5.2.2: Else
Step [Link]: Push input[i] onto stack
Step [Link]: Increment i by 1
Step [Link]: Print stack, remaining input, and "Shift current symbol"
Step 5.2.3: Call reduce()
Step 5.2.4: Print stack and remaining input after reduction
Step 6: Final reduction
Step 6.1: Call reduce() one last time
Step 7: Acceptance check
Step 7.1: If top == 0 and stack[top] == 'E', print "Accepted: The input string is valid as per
the grammar."
Step 7.2: Else, print "Rejected: The input string is invalid."
Step 8: Stop
CALCULATOR
ALGORITHM FOR LEX PROGRAM:
Step 1: Start
Step 2: Include the required header files <stdio.h> and "[Link].h"
Step 3: Declare yylval as an external variable to hold numeric values for tokens
Step 4: Define the lexical rules:
Step 4.1: If the input matches a sequence of digits [0-9]+, convert it into an integer using
atoi(yytext), store it in yylval, and return the token NUMBER
Step 4.2: If the input is a tab character [\t], ignore it (do nothing)
Step 4.3: If the input is a newline character [\n], return 0 to indicate end of input
Step 4.4: For any other single character ., return that character itself (yytext[0])
Step 5: Continue scanning input characters until the end of file is reached
Step 6: Call the function yywrap() after finishing input, which returns 1 to indicate no more
input remains
Step 7: Stop
ALGORITHM FOR YACC PROGRAM:
Step 1: Start
Step 2: Include the standard header file <stdio.h> and declare a global variable flag = 0 to
track validity of the expression
Step 3: Define the token NUMBER to represent numeric values
Step 4: Specify operator precedence and associativity:
Step 4.1: '+' and '-' have left associativity
Step 4.2: '*', '/', and '%' have left associativity
Step 4.3: Parentheses '(' and ')' are also defined with precedence
Step 5: Define the grammar rules:
Step 5.1: ArithmeticExpression → E
On successful reduction, print the result and return 0
Step 5.2: E → E + E compute value as $1 + $3
Step 5.3: E → E - E compute value as $1 - $3
Step 5.4: E → E * E compute value as $1 * $3
Step 5.5: E → E / E compute value as $1 / $3
Step 5.6: E → E % E compute value as $1 % $3
Step 5.7: E → ( E ) value is $2
Step 5.8: E → NUMBER value is $1
Step 6: In the main function:
Step 6.1: Print a message asking the user to enter an arithmetic expression
Step 6.2: Call yyparse() to start parsing
Step 6.3: If flag == 0, print that the expression is valid
Step 7: If a syntax error occurs, call yyerror():
Step 7.1: Print that the entered expression is invalid
Step 7.2: Set flag = 1
Step 8: Stop
ALGORITHM LEXICAL ANALYSER
Step 1: Start
Step 2: Define the function isKeyword(word)
→ Compare word with known C keywords: int, while, if, return, else.
→ If match found, return 1, else return 0.
Step 3: Define token patterns in the LEX rules section (%% ... %%).
Step 4: Specify the following rules:
Rule 1: [0-9]+
→ Print "NUMBER: yytext".
→ Recognizes numeric constants.
Rule 2: [a-zA-Z_][a-zA-Z0-9_]*
→ If isKeyword(yytext) returns 1 → Print "KEYWORD: yytext".
→ Else → Print "IDENTIFIER: yytext".
Rule 3: [+\-*/=<>]
→ Print "OPERATOR: yytext".
Rule 4: [\(\)\{\}]
→ Print "PARENTHESIS: yytext".
Rule 5: [ \t\n]
→ Ignore whitespace characters.
Rule 6: .
→ Print "UNKNOWN: yytext" for any other symbol.
Step 5: Define yywrap() function to return 1 indicating end of input.
Step 6: In main() function:
→ Print message "Enter your input (press Ctrl+D to end):".
→ Call yylex() to begin lexical analysis.
→ Return 0 to indicate successful completion.
Step 7: Stop