Questions tagged [lexical-analysis]
The lexical-analysis tag has no usage guidance.
41 questions
1
vote
1
answer
56
views
Possible mistake in a book regarding parsing and lexical analysis
I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage :
"From a practical point of view, for each grammar G = (Σ,V, S, P) ...
- 33
0
votes
1
answer
44
views
C language tokenizer output for static integer array
Unable to find out how the C-language lexical analyzer would tokenize the declaration of a static array. Say, int i[3]= {1,2,3};
The lexical analyzer would need to differentiate between just an ...
- 187
1
vote
0
answers
101
views
How to develop intuition to come up with Context Free Grammar?
So i'm taking this class automata and complexity at georgia tech and we were given practice material for our exam.
one of the question is to give context free grammar for these two languages
and the ...
- 11
0
votes
0
answers
138
views
Is there any way to tell which states are final states in a finite state automata given only its grammar?
Problem
In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
0
votes
1
answer
934
views
Should I lookahead in the lexer or parser?
So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions.
While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a ...
- 115
1
vote
1
answer
279
views
How do I find the regular expression for- All binary numbers greater than 110011
I am trying to solve a problem set to practice for an exam. How can I approach questions like these ? Is there a way to verify solutions or is it just trial and error ?
- 111
1
vote
1
answer
94
views
What are good alternatives to the table-driven approach to lexical analysis?
In my theoretical computer science class we learned about FSMs/lexical analysis/parsing. However, my teacher focused solely on the table-driven approach to the process for simplicity (I think, anyway),...
- 13
1
vote
3
answers
90
views
Variable name starting with integers
When I started doing programming I wondered that why the variable names can't start with integer. Back then I accepted that , may be this is how the compiler designers have decided to go with. But now ...
- 305
0
votes
1
answer
199
views
How are lexical tokens produced
I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, ...
- 305
2
votes
2
answers
818
views
What defines how many lookahead a lexer has?
if a lexical grammar has multiple token which start with the same character like > >> ...
- 21
0
votes
0
answers
29
views
Immutable lexical scope data structure
I'm working on a mini lisp and now I'm wonder about scopes. For my case I'll have this constructs that introduce scopes.
lambdas introduce it's arguments
let binds
and modules
The way I worked on ...
- 253
1
vote
1
answer
656
views
What makes a nested function in gcc so complicated?
Disclaimer: I'm not a compiler expert, but some of my best friends are! :)
I do a lot of embedded systems programming where stack (and other memory) is limited. Most of my code is written in gcc, ...
- 445
1
vote
1
answer
371
views
Understanding lexical grammar for multi-line comments in JavaCC
I'm struggling to understand why this piece of lexical grammar works for multi-line comments in JavaCC (posted here):
...
- 11
1
vote
1
answer
628
views
Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?
I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.
However, I've encountered this statement from my notes:
With $\epsilon$ productions in the ...
- 157
0
votes
1
answer
2k
views
Table-Driven Lexer and the Classification Table
I'm trying to implement a compiler for a custom language as part of an assignment.
I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 ...
- 157
0
votes
2
answers
419
views
To remove all comments in a JavaScript file, do we need just a scanner or also a parser?
I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string:
...
- 413
1
vote
1
answer
99
views
does a non-terminated string count as a token in c?
so, I am preparing for an exam which includes lexical analysis from compiler design. I was wondering what is the number of tokens in the following code-
...
- 57
5
votes
2
answers
1k
views
Finding the number of distinct strings in regular expression
Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
- 53
0
votes
1
answer
56
views
Is scanner and Lexical analyzer same?
Today I read that
The scanner is a subroutine which is frequently called by an
application program like a compiler. The primary function of a scanner
is to combine characters from the input ...
user106464
2
votes
0
answers
49
views
CYK algorithm - how to handle unknown terminals given in a sentence to parse?
There is a given treebank which we derive the Probabilistic context free grammar.
I wonder how do one handles with a given sentence which includes terminals that don't exist in the derived rules?
Is ...
- 181
2
votes
1
answer
862
views
Lexicographically smallest down-right path in matrix
Here is the problem which I thought was simple dynamic programming, which is however not the case.
Given an $N \times M$ matrix of numbers from 1 to $NM$ (each number occurs only once), find a path ...
user99043
2
votes
1
answer
176
views
Why are regular expression used in lexical analysis instead of grammars?
Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?
- 23
0
votes
1
answer
317
views
Token Scanner for programming Language(Lexical Analysis)
This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them.
The ...
1
vote
1
answer
2k
views
How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold ...
- 283
0
votes
1
answer
516
views
Counting tokens in compilers, lexical analyser
Let's start with the question. Say I have a C language statements follows
it 458cat 2.01 = 96.87abc a.2 ;
-my question is how many tokens are there in the above statements. Secondly does white ...
- 329
0
votes
0
answers
266
views
What token does a "peek" operation refer to in Lexical analysis?
Given a grammar for a space delimited list of words:
S -> word { space word }
word -> [a-zA-Z]+
space -> [ \t]+
And given the input "Hello World", ...
- 283
1
vote
1
answer
2k
views
Lexical analysis and reserved words
My book says lexical analysis detects reserved words.
How can lexical analysis detect whether we are using reserved words in incorrect places ?
For eg :- while(a>0) and int while = 5.
How can ...
- 319
0
votes
1
answer
127
views
Do we need regular expression first or finite state automata in lexical anlysing? [closed]
I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, ...
- 103
0
votes
1
answer
8k
views
How does lexical analyzer remove white spaces from source file?
In compiler at phase lexical analyzer, how does lexical analyze strip out white spaces from source file?.
- 143
3
votes
3
answers
859
views
Thompson's construction, transforming a regular expression into an equivalent NFA
There is this case of concatenation that says (from wikipedia):
The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final ...
- 259
3
votes
1
answer
2k
views
Why using finite automata in implementing lexical analyzers
I studied the subject of building a lexical analyzer using finite automata, through the classical way: Regular Expression -> NDA -> DFA. And I found it elegant, and a more solid approach for building ...
- 259
2
votes
1
answer
1k
views
How do hand-written lexers work?
Im studying a book called "Engineering a compiler" by Linda Torczon and Margaret Cooper. In the second chapter which discusses lexical analysis they mention three aproaches to writing a lexical ...
- 165
3
votes
1
answer
2k
views
White-space and comment by lexical analyzer
Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in ...
- 135
4
votes
3
answers
1k
views
Why do we not use CFGs to describe the structure of lexical tokens?
This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff.
Here is my current answer:
CFGs describe how non-terminal symbols are converted into ...
- 203
5
votes
2
answers
2k
views
What is the point of delimiters and whitespace handling
I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
1
vote
1
answer
395
views
What is token-type in Lexical analysis?
I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 .
i cannot understand what is this kind of ...
- 165
1
vote
1
answer
568
views
Why the given lexical specification will not process the following strings?
I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question.
Here ...
- 1,233
2
votes
1
answer
109
views
Prefix computation used for lexical analysis?
I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms.
Several lists of ...
- 203
0
votes
3
answers
3k
views
What data is stored in the symbol table for a number token?
I'm reading the Dragon Book. The following is from the start of Section 3.1.3.
When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases ...
- 131
1
vote
2
answers
108
views
Trying to understand a token file for lexical analysis
I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines:
...
- 1,809
8
votes
4
answers
2k
views
Are there real lexers that use NFAs directly instead of first transforming them to DFAs?
I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
- 181