diff --git a/cc/cc.go b/cc/cc.go
index 0d5b6bd..53528af 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -116,6 +116,8 @@
 	// Used for host bionic
 	LinkerFlagsFile string
 	DynamicLinker   string
+
+	Tools []string
 }
 
 type PathDeps struct {
@@ -158,6 +160,8 @@
 
 	// Path to the dynamic linker binary
 	DynamicLinker android.OptionalPath
+
+	Tools map[string]android.Path
 }
 
 // LocalOrGlobalFlags contains flags that need to have values set globally by the build system or locally by the module
@@ -425,6 +429,12 @@
 	XrefCcFiles() android.Paths
 }
 
+type ToolDependencyTag struct {
+	blueprint.BaseDependencyTag
+
+	Name string
+}
+
 var (
 	dataLibDepTag         = DependencyTag{Name: "data_lib", Library: true, Shared: true}
 	sharedExportDepTag    = DependencyTag{Name: "shared", Library: true, Shared: true, ReexportFlags: true}
@@ -1694,6 +1704,7 @@
 	deps.LateSharedLibs = android.LastUniqueStrings(deps.LateSharedLibs)
 	deps.HeaderLibs = android.LastUniqueStrings(deps.HeaderLibs)
 	deps.RuntimeLibs = android.LastUniqueStrings(deps.RuntimeLibs)
+	deps.Tools = android.LastUniqueStrings(deps.Tools)
 
 	for _, lib := range deps.ReexportSharedLibHeaders {
 		if !inList(lib, deps.SharedLibs) {
@@ -2037,6 +2048,11 @@
 			}, vndkExtDepTag, vndkdep.getVndkExtendsModuleName())
 		}
 	}
+
+	for _, tool := range deps.Tools {
+		actx.AddFarVariationDependencies(ctx.Config().BuildOSTarget.Variations(),
+			ToolDependencyTag{Name: tool}, tool)
+	}
 }
 
 func BeginMutator(ctx android.BottomUpMutatorContext) {
@@ -2219,6 +2235,21 @@
 		depName := ctx.OtherModuleName(dep)
 		depTag := ctx.OtherModuleDependencyTag(dep)
 
+		if toolDep, ok := depTag.(ToolDependencyTag); ok {
+			if toolMod, ok := dep.(android.HostToolProvider); ok {
+				if depPaths.Tools == nil {
+					depPaths.Tools = make(map[string]android.Path)
+				}
+				toolPath := toolMod.HostToolPath()
+				if !toolPath.Valid() {
+					ctx.ModuleErrorf("Failed to find path for host tool %q", toolDep.Name)
+				}
+				depPaths.Tools[toolDep.Name] = toolPath.Path()
+			} else {
+				ctx.ModuleErrorf("Found module, but not host tool for %q", toolDep.Name)
+			}
+		}
+
 		ccDep, ok := dep.(LinkableInterface)
 		if !ok {
 
diff --git a/cc/compiler.go b/cc/compiler.go
index d5ea2c3..ba14dd5 100644
--- a/cc/compiler.go
+++ b/cc/compiler.go
@@ -251,6 +251,14 @@
 		deps.StaticLibs = append(deps.StaticLibs, "libomp")
 	}
 
+	if compiler.hasSrcExt(".y") || compiler.hasSrcExt(".yy") {
+		deps.Tools = append(deps.Tools, "bison", "m4")
+	}
+
+	if compiler.hasSrcExt(".l") || compiler.hasSrcExt(".ll") {
+		deps.Tools = append(deps.Tools, "flex", "m4")
+	}
+
 	return deps
 }
 
@@ -581,7 +589,7 @@
 
 	srcs := append(android.Paths(nil), compiler.srcsBeforeGen...)
 
-	srcs, genDeps := genSources(ctx, srcs, buildFlags)
+	srcs, genDeps := genSources(ctx, srcs, buildFlags, deps.Tools)
 	pathDeps = append(pathDeps, genDeps...)
 
 	compiler.pathDeps = pathDeps
diff --git a/cc/gen.go b/cc/gen.go
index b0aadc6..6f9036b 100644
--- a/cc/gen.go
+++ b/cc/gen.go
@@ -24,7 +24,6 @@
 )
 
 func init() {
-	pctx.SourcePathVariable("lexCmd", "prebuilts/build-tools/${config.HostPrebuiltTag}/bin/flex")
 	pctx.SourcePathVariable("m4Cmd", "prebuilts/build-tools/${config.HostPrebuiltTag}/bin/m4")
 
 	pctx.HostBinToolVariable("aidlCmd", "aidl-cpp")
@@ -32,12 +31,6 @@
 }
 
 var (
-	lex = pctx.AndroidStaticRule("lex",
-		blueprint.RuleParams{
-			Command:     "M4=$m4Cmd $lexCmd -o$out $in",
-			CommandDeps: []string{"$lexCmd", "$m4Cmd"},
-		})
-
 	sysprop = pctx.AndroidStaticRule("sysprop",
 		blueprint.RuleParams{
 			Command: "$syspropCmd --header-dir=$headerOutDir --public-header-dir=$publicOutDir " +
@@ -66,7 +59,8 @@
 }
 
 func genYacc(ctx android.ModuleContext, rule *android.RuleBuilder, yaccFile android.Path,
-	outFile android.ModuleGenPath, props *YaccProperties) (headerFiles android.Paths) {
+	outFile android.ModuleGenPath, props *YaccProperties,
+	tools map[string]android.Path) (headerFiles android.Paths) {
 
 	outDir := android.PathForModuleGen(ctx, "yacc")
 	headerFile := android.GenPathWithExt(ctx, "yacc", yaccFile, "h")
@@ -97,9 +91,17 @@
 		}
 	}
 
-	cmd.Text("BISON_PKGDATADIR=prebuilts/build-tools/common/bison").
-		FlagWithInput("M4=", ctx.Config().PrebuiltBuildTool(ctx, "m4")).
-		PrebuiltBuildTool(ctx, "bison").
+	bison, ok := tools["bison"]
+	if !ok {
+		ctx.ModuleErrorf("Unable to find bison")
+	}
+	m4, ok := tools["m4"]
+	if !ok {
+		ctx.ModuleErrorf("Unable to find m4")
+	}
+
+	cmd.FlagWithInput("M4=", m4).
+		Tool(bison).
 		Flag("-d").
 		Flags(flags).
 		FlagWithOutput("--defines=", headerFile).
@@ -153,13 +155,23 @@
 	}
 }
 
-func genLex(ctx android.ModuleContext, lexFile android.Path, outFile android.ModuleGenPath) {
-	ctx.Build(pctx, android.BuildParams{
-		Rule:        lex,
-		Description: "lex " + lexFile.Rel(),
-		Output:      outFile,
-		Input:       lexFile,
-	})
+func genLex(ctx android.ModuleContext, rule *android.RuleBuilder, lexFile android.Path,
+	outFile android.ModuleGenPath, tools map[string]android.Path) {
+
+	flex, ok := tools["flex"]
+	if !ok {
+		ctx.ModuleErrorf("Unable to find flex")
+	}
+	m4, ok := tools["m4"]
+	if !ok {
+		ctx.ModuleErrorf("Unable to find m4")
+	}
+
+	rule.Command().
+		FlagWithInput("M4=", m4).
+		Tool(flex).
+		FlagWithOutput("-o", outFile).
+		Input(lexFile)
 }
 
 func genSysprop(ctx android.ModuleContext, syspropFile android.Path) (android.Path, android.Paths) {
@@ -206,14 +218,22 @@
 	return rcFile, headerFile
 }
 
-func genSources(ctx android.ModuleContext, srcFiles android.Paths,
-	buildFlags builderFlags) (android.Paths, android.Paths) {
+func genSources(ctx android.ModuleContext, srcFiles android.Paths, buildFlags builderFlags,
+	tools map[string]android.Path) (android.Paths, android.Paths) {
 
 	var deps android.Paths
 	var rsFiles android.Paths
 
 	var aidlRule *android.RuleBuilder
 
+	var lexRule_ *android.RuleBuilder
+	lexRule := func() *android.RuleBuilder {
+		if lexRule_ == nil {
+			lexRule_ = android.NewRuleBuilder().Sbox(android.PathForModuleGen(ctx, "lex"))
+		}
+		return lexRule_
+	}
+
 	var yaccRule_ *android.RuleBuilder
 	yaccRule := func() *android.RuleBuilder {
 		if yaccRule_ == nil {
@@ -227,19 +247,19 @@
 		case ".y":
 			cFile := android.GenPathWithExt(ctx, "yacc", srcFile, "c")
 			srcFiles[i] = cFile
-			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cFile, buildFlags.yacc)...)
+			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cFile, buildFlags.yacc, tools)...)
 		case ".yy":
 			cppFile := android.GenPathWithExt(ctx, "yacc", srcFile, "cpp")
 			srcFiles[i] = cppFile
-			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cppFile, buildFlags.yacc)...)
+			deps = append(deps, genYacc(ctx, yaccRule(), srcFile, cppFile, buildFlags.yacc, tools)...)
 		case ".l":
 			cFile := android.GenPathWithExt(ctx, "lex", srcFile, "c")
 			srcFiles[i] = cFile
-			genLex(ctx, srcFile, cFile)
+			genLex(ctx, lexRule(), srcFile, cFile, tools)
 		case ".ll":
 			cppFile := android.GenPathWithExt(ctx, "lex", srcFile, "cpp")
 			srcFiles[i] = cppFile
-			genLex(ctx, srcFile, cppFile)
+			genLex(ctx, lexRule(), srcFile, cppFile, tools)
 		case ".proto":
 			ccFile, headerFile := genProto(ctx, srcFile, buildFlags)
 			srcFiles[i] = ccFile
@@ -271,6 +291,10 @@
 		aidlRule.Build(pctx, ctx, "aidl", "gen aidl")
 	}
 
+	if lexRule_ != nil {
+		lexRule_.Build(pctx, ctx, "lex", "gen lex")
+	}
+
 	if yaccRule_ != nil {
 		yaccRule_.Build(pctx, ctx, "yacc", "gen yacc")
 	}