I. Feasible and Realizable Paths

1. Feasible

Infeasible Paths: Paths in CFG that do not correspond to actual executions

• We hope that program analysis results could not be polluted, or polluted as little as possible, by infeasible paths.
• But given a path, determine whether it is feasible is, in general, undecidable.

2. Realizable

Realizable Paths: The paths in which “returns” are matched with corresponding “calls”

• Realizable paths may not be executable, but unrealizable paths must not be executable.
• Our goal is to recognize realizable paths so that we could avoid polluting analysis results along unrealizable paths.

Basic idea: balanced-parenthesis

II. CFL-Reachability

A systematical way to recognize realizable paths

1. Definition

CFL-Reachability: A path is considered to connect two nodes A and B, or B is reachable from A, only if the concatenation of the labels on the edges of the path is a word in a specified context-free language.

2. Partially Balanced-Parenthesis Problem via CFL

• Every right parenthesis “$\tt )_i$ ” is balanced by a preceding left parenthesis “$\tt (_i$ ”, but the converse needs not hold

• For each call site i, label its call edge “$\tt (_i$ ” and return edge “$\tt )_i$ ”

• Label all other edges with symbol “$\tt e$”

A path is a realizable path iff the path’ word is in the language $\blue {L(realizable)}$