Provide an unambiguous context-free grammar for a language $L$

421 Views Asked by At

Firstly, let $L = \{ w \in \Sigma \cup \{ \varepsilon, (,), +, ., ^* \}^* \mid w $ is a syntactically legal regular expression over $\Sigma \} $.

I need to give an unambiguous context-free grammar that generates L. The question notes that the grammar should use the following precedence levels, from highest to lowest: (1) $^*$ (Kleene star), (2) $.$ (concatenation), and (3) $+$ (union).

While this makes sense, I am unclear on precedence.

The question goes on to ask for a parse tree for the newly created grammar that produces for the string $a(a+b)^*$ .

Does anyone know where to begin with this? I feel like I understand context-free grammars but ensuring unambiguous and precedence is a bit confusing.